← Real problems

egoi22p3

unratedStatement on DMOJ

CP Lang

31 lineschecks
// EGOI 2022 "Social Engineering": Maria (vertex 1) and an adversary walk a
// graph without reusing edges; whoever cannot move loses. Win if possible.
// Without vertex 1, pair up the friends of 1 by edge-disjoint paths through a
// DFS forest; if one is left unpaired Maria starts there, otherwise she answers
// each adversary move into a friend along its paired path back home.
extern fn get_move() -> Int
extern fn make_move(v: Int)

@grader
fn social_engineering(n: Int, edges: List<(Int, Int)>):
    domain V = 1..=n
    let g = Graph.undirected([edges.keys] e => (u: V(edges[e].0), v: V(edges[e].1)))
    let home = V.first!
    let friend = V.mask(g.next(home))
    let forest = Rooted.forest(g.only(v => v != home), from: List(g.next(home)))
    var route = Map<V, List<V>>()

    fn pair_up(u: V) -> ?List<V>:
        let open = List(chain(if friend[u]: [List<V>()] else: [], forest.children(u).filter_map(pair_up)))
        for pair in open.chunks(2) if pair.len == 2:
            let path = pair[0] + [u] + pair[1].rev
            route[path.first!] = path
            route[path.last!] = path.rev
        open.len.is_odd().then(open.last! + [u])

    if forest.roots.any(r => pair_up(r).is_some()):
        return
    while let u = V.at(get_move()):
        for v in route[u].drop(1):
            make_move(Int(v))
        make_move(Int(home))

Accepted C++

236 lines · 5.50 s on the judge
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

template <typename T>
ostream& operator<<(ostream& out, const vector<T>& arr) {
    for (int i = 0; i < sz(arr); i++) {
        if (i) {
            out << " ";
        }
        out << arr[i];
    }
    return out;
}

struct Grader {
    int n, m, cu = 1;
    mt19937 cowng;
    set<pair<int, int>> edges;

    Grader() {}
    Grader(int n, int m, const vector<pair<int, int>>& _edges) : n(n), m(m) {
        for (auto& [u, v] : _edges) {
            edges.emplace(u, v);
            edges.emplace(v, u);
        }
        int seed;
        cin >> seed;
        cowng = mt19937(seed);
    }

    void m_make_move(int v) {
        assert(edges.count({cu, v}));
        edges.erase({cu, v});
        edges.erase({v, cu});
        cu = v;
    }

    int get_move() {
        assert(cu == 1);
        vector<int> adj;
        for (auto& [u, v] : edges) {
            if (u == 1) {
                adj.push_back(v);
            }
        }
        if (!sz(adj)) {
            return 0;
        }
        int u = adj[cowng() % sz(adj)];
        m_make_move(u);
        return u;
    }

    void make_move(int v) {
        m_make_move(v);
    }
} grader;

#ifdef LOCAL
int GetMove() {
    return grader.get_move();
}
void MakeMove(int v) {
    grader.make_move(v);
}
#else
int GetMove();
void MakeMove(int v);
#endif

int get_move() {
    int ans = GetMove() - 1;
    dbg("G", ans);
    return ans;
}

void make_move(int v) {
    dbg("M", v);
    MakeMove(v + 1);
}

template <typename T>
T reversed(T t) {
    reverse(begin(t), end(t));
    return t;
}

constexpr int maxn = 2e5 + 5;

vector<int> graph[maxn], tree[maxn];
int cnt1 = 0, par[maxn];
bool vis1[maxn], special[maxn];
vector<vector<int>> pairings;

void dfs1(int u, int p) {
    if (!u || vis1[u]) {
        return;
    }
    par[u] = p;
    if (p != -1) {
        tree[p].push_back(u);
    }
    vis1[u] = true;
    cnt1 += special[u];
    for (auto& v : graph[u]) {
        dfs1(v, u);
    }
}

int dfs2(int u) {
    vector<int> ch;
    if (special[u]) {
        ch.push_back(u);
    }
    for (auto& v : tree[u]) {
        auto cv = dfs2(v);
        if (cv != -1) {
            ch.push_back(cv);
        }
    }
    for (int i = 0; i + 1 < sz(ch); i += 2) {
        vector<int> cur;
        auto go = [&](int v) -> void {
            while (u != v) {
                cur.push_back(v);
                v = par[v];
            }
        };
        go(ch[i]);
        auto tmp = reversed(cur);
        cur.clear();
        go(ch[i + 1]);
        cur.push_back(u);
        cur.insert(cur.end(), begin(tmp), end(tmp));
        pairings.push_back(cur);
    }
    if (sz(ch) % 2) {
        return ch.back();
    } else {
        return -1;
    }
}

void SocialEngineering(int, int, vector<pair<int, int>> edges) {
    for (auto& [u, v] : edges) {
        u--;
        v--;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    if (sz(graph[0]) % 2) {
        return;
    }
    for (auto& u : graph[0]) {
        special[u] = true;
    }
    vector<int> roots;
    for (auto& u : graph[0]) {
        if (vis1[u]) {
            continue;
        }
        roots.push_back(u);
        dfs1(u, -1);
        if (cnt1 % 2) {
            return;
        }
    }
    for (auto& a : roots) {
        dfs2(a);
    }
    map<int, vector<int>> mp;
    for (auto& a : pairings) {
        dbg(pairings);
        mp[a[0]] = a;
        mp[a.back()] = reversed(a);
    }
    while (true) {
        int u = get_move();
        if (u == -1) {
            return;
        }
        auto& cans = mp[u];
        for (auto& v : cans) {
            if (u != v) {
                make_move(v);
            }
        }
        make_move(0);
    }
}

void solve() {
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> edges(m);
    for (auto& [u, v] : edges) {
        cin >> u >> v;
    }
    grader = Grader(n, m, edges);
    SocialEngineering(n, m, edges);
}

int main() {
    cin.tie(nullptr);
    cin.exceptions(ios::failbit);
    ios_base::sync_with_stdio(false);
    solve();
}