Submission #1259081

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259081		biank	Sphinx's Riddle (IOI24_sphinx)	C++20	100 / 100	950 ms	1636 KiB

sphinx

#include "sphinx.h"
#include <bits/stdc++.h>
 
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
 
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
 
#define pb push_back
#define eb emplace_back
 
#define fst first
#define snd second
 
using namespace std;
 
using vi = vector<int>;
using ii = pair<int, int>;
using ll = long long;

struct DSU {
    vi p;
    DSU(int n) : p(n, -1) {}
    int find(int x) {
        if (p[x] < 0) return x;
        return p[x] = find(p[x]);
    }
    bool unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return false;
        if (p[x] > p[y]) swap(x, y);
        return p[x] += p[y], p[y] = x, true;
    }
};

vector<vi> eraseEmpty(const vector<vi> &a) {
    vector<vi> b;
    for (auto v : a) if (!v.empty()) b.pb(v);
    return b;
}

void dfsParity(int u, vi &type, const vector<vi> &adj, vector<vi> &euler) {
    for (int v : adj[u]) if (!type[v]) {
        type[v] = 3 - type[u];
        euler[type[v]].pb(v);
        dfsParity(v, type, adj, euler);
    }
}

const int UNKNOWN = 1e9 + 7;

vi find_colours(int N, vi X, vi Y) {
    const int M = sz(X);
    vector<vi> adj(N);
    forn(i, M) {
        adj[X[i]].pb(Y[i]);
        adj[Y[i]].pb(X[i]);
    }
    DSU dsu(N);
    vi color(N, UNKNOWN);
    auto expected = [&](const vi &E) {
        queue<int> q;
        vector<bool> vis(N, false);
        int cmps = 0;
        forn(j, N) if (!vis[j]) {
            q.push(j), cmps++, vis[j] = true;
            while (!q.empty()) {
                int u = q.front();
                q.pop();
                for (int v : adj[u]) {
                    if (vis[v]) continue;
                    if ((E[u] == E[v] && E[u] != -1) ||
                        (E[u] == E[v] && dsu.find(u) == dsu.find(v)) ||
                        (E[u] == -1 && color[dsu.find(u)] == E[v]) ||
                        (E[v] == -1 && color[dsu.find(v)] == E[u])) {
                        q.push(v), vis[v] = true;
                    }
                }
            }
        }
        return cmps;
    };
    forsn(i, 1, N) while (true) {
        vector<vi> comps(i);
        for (int j : adj[i]) if (j < i) {
            int p = dsu.find(j);
            assert(p < i);
            comps[p].pb(j);
        }
        comps = eraseEmpty(comps);
        auto check = [&](int k) {
            vi E = vi(N, N);
            E[i] = -1;
            forn(idx, k) for (int j : comps[idx]) E[j] = -1;
            return perform_experiment(E) == expected(E);
        };
        if (check(sz(comps))) break;
        int lo = 0, hi = sz(comps);        
        while (hi - lo > 1) {
            int mid = (lo + hi) / 2;
            if (check(mid)) lo = mid;
            else hi = mid;
        }
        dsu.unite(comps[lo].back(), i);
    }
    vector<vi> adjC(N);
    forn(i, M) {
        int x = dsu.find(X[i]), y = dsu.find(Y[i]);
        if (x != y) adjC[x].pb(y), adjC[y].pb(x);
    }
    forn(u, N) {
        sort(all(adjC[u]));
        adjC[u].erase(unique(all(adjC[u])), end(adjC[u]));
    }
    vi type(N, 0);
    vector<vi> euler(3);
    type[0] = 1;
    euler[1].pb(0);
    dfsParity(0, type, adj, euler);
    forsn(t, 1, 3) forn(c, N) while (true) {
        auto check = [&](int k) {
            vi E(N, N);
            for (int u : euler[3 - t]) E[u] = c;
            forn(idx, k) E[euler[t][idx]] = -1;
            return perform_experiment(E) == expected(E);
        };
        if (check(sz(euler[t]))) break;
        int lo = 0, hi = sz(euler[t]);
        while (hi - lo > 1) {
            int mid = (lo + hi) / 2;
            if (check(mid)) lo = mid;
            else hi = mid;
        }
        color[dsu.find(euler[t][lo])] = c;
    }
    vi C(N);
    forn(i, N) C[i] = color[dsu.find(i)];
    return C;
}

• Subtask 0: 0 / 0
• Subtask 1: 3 / 3
• Subtask 2: 7 / 7
• Subtask 3: 33 / 33
• Subtask 4: 21 / 21
• Subtask 5: 36 / 36