Submission #1249204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249204		qwerasdfzxcl	Sphinx's Riddle (IOI24_sphinx)	C++20	100 / 100	884 ms	1616 KiB

sphinx

#include "sphinx.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct DSU{
    int path[2020], col[2020];

    void init(int n){
        for (int i=0;i<n;i++) path[i] = i, col[i] = i + 2020;
    }

    int find(int s){
        if (s==path[s]) return s;
        return path[s] = find(path[s]);
    }

    int merge(int x, int y){
        x = find(x), y = find(y);
        if (x==y) return 0;
        path[x] = y;
        return 1;
    }

    int getcol(int s){return col[find(s)];}
    void setcol(int s, int c){col[find(s)] = c;}
}dsu, dsu2;

int N, tmp;
vector<int> X, Y;

int predict(vector<int> Q){
    int ret = N;
    dsu2.init(N);

    for (int i=0;i<(int)X.size();i++){
        int cx = Q[X[i]], cy = Q[Y[i]];
        if (cx == -1) cx = dsu.getcol(X[i]);
        if (cy == -1) cy = dsu.getcol(Y[i]);

        if (cx == cy) ret -= dsu2.merge(X[i], Y[i]);
    }

    return ret;
}

int query(vector<int> Q, bool flag = false){
    int ret = predict(Q);

    if (flag){
        tmp = perform_experiment(Q);
        ret -= tmp;
    } 
    else ret -= perform_experiment(Q);
    
    assert(ret >= 0);
    
    return ret;
}

std::vector<int> find_colours(int N, std::vector<int> X, std::vector<int> Y) {
    ::N = N, ::X = X, ::Y = Y;
    dsu.init(N);

    // phase 1 (50 points)
    for (int i=0;i<N;i++){
        vector<int> Q(N, N);
        for (int j=0;j<=i;j++) Q[j] = -1;

        int t = query(Q);
        
        while(t--){
            vector<int> adj;
            
            for (int j=0;j<(int)X.size();j++){
                int x = dsu.find(X[j]), y = dsu.find(Y[j]);
                if (x == y) continue;
                if (x == dsu.find(i) && y < i) adj.push_back(y);
                if (x < i && y == dsu.find(i)) adj.push_back(x);
            }

            sort(adj.begin(), adj.end());
            adj.erase(unique(adj.begin(), adj.end()), adj.end());

            int l = 0, r = (int)adj.size() - 1, v = (int)adj.size();
            while(l<=r){
                int mid = (l+r)>>1;
                vector<int> Q(N, N);

                for (int j=0;j<N;j++){
                    if (dsu.find(j) == dsu.find(i)) Q[j] = -1;
                    if (find(adj.begin(), adj.end(), dsu.find(j)) - adj.begin() <= mid) Q[j] = -1;
                }

                if (query(Q) > 0) r = mid-1, v = mid;
                else l = mid+1;
            }

            if (v == (int)adj.size()){
                if (query(Q) == 0) return {};
            }
            assert(v < (int)adj.size());
            dsu.merge(i, adj[v]);
        }
    }

    // phase 2
    int is_one = 1;
    for (int i=0;i<N;i++) if (dsu.find(0) != dsu.find(i)) is_one = 0;

    if (is_one){
        for (int i=0;i<N;i++){
            vector<int> Q(N, -1);
            Q[0] = i;
            if (perform_experiment(Q) == 1) dsu.setcol(0, i);
        }
        return vector<int>(N, dsu.getcol(0));
    }

    vector<vector<int>> adj(N), buf(2);
    vector<int> typ(N, -1);

    for (int i=0;i<(int)X.size();i++){
        adj[dsu.find(X[i])].push_back(dsu.find(Y[i]));
        adj[dsu.find(Y[i])].push_back(dsu.find(X[i]));
    }

    auto dfs = [&](auto self, int s, int c) -> void {
        typ[s] = c;
        buf[c].push_back(s);
        
        for (auto &v:adj[s]) if (typ[v] == -1) self(self, v, c^1);
    };

    dfs(dfs, dsu.find(0), 0);

    for (int z=0;z<2;z++){
        for (int c=0;c<N;c++){
            vector<int> Q(N, -1);
            for (int i=0;i<N;i++) if (typ[dsu.find(i)] != z) Q[i] = c;

            query(Q, true);
            
            while(true){
                fill(Q.begin(), Q.end(), -1);
                for (int i=0;i<N;i++) if (typ[dsu.find(i)] != z) Q[i] = c;
                if (tmp == predict(Q)) break;

                int l = 0, r = (int)buf[z].size() - 1, v = (int)buf[z].size();
                while(l <= r){
                    int mid = (l+r)>>1;
                    
                    for (int i=0;i<N;i++) if (typ[dsu.find(i)] == z){
                        if (find(buf[z].begin(), buf[z].end(), dsu.find(i)) - buf[z].begin() <= mid) Q[i] = -1;
                        else Q[i] = N;
                    }

                    if (query(Q) > 0) r = mid-1, v = mid;
                    else l = mid+1;
                }

                assert(v < (int)buf[z].size());
                dsu.setcol(buf[z][v], c);
            }
        }
    }

    vector<int> ret(N);
    for (int i=0;i<N;i++) ret[i] = dsu.getcol(i);
    
    return ret;
}

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