Submission #1202028

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202028		Nelt	Sphinx's Riddle (IOI24_sphinx)	C++20	Compilation error	0 ms	0 KiB

sphinx

struct DSU {
    vector<int> p;
    DSU(int n): p(n) { iota(p.begin(),p.end(),0); }
    int find(int x){ return p[x]==x?x:p[x]=find(p[x]); }
    void unite(int a,int b){
        a=find(a); b=find(b);
        if(a!=b) p[b]=a;
    }
};

vector<int> find_colours(int N, vector<int> X, vector<int> Y) {
    int M = X.size();
    DSU dsu(N);

    vector<int> E(N);
    // for each edge test if its endpoints share the same original colour
    for(int j = 0; j < M; j++){
        int u = X[j], v = Y[j];
        // recolour everyone to Sphinx (colour N), except u and v keep original
        fill(E.begin(), E.end(), N);
        E[u] = E[v] = -1;
        int comps = perform_experiment(E);
        // If we see exactly 2 monochromatic components,
        // u and v must have merged into one ⇒ same original colour
        if(comps == 2) {
            dsu.unite(u, v);
        }
        // else (comps == 3) they stayed separate ⇒ different colours
    }

    // now assign each DSU component an arbitrary label in [0..N)
    vector<int> comp_id(N, -1), G(N);
    int next_label = 0;
    for(int i = 0; i < N; i++){
        int r = dsu.find(i);
        if(comp_id[r] < 0) 
            comp_id[r] = next_label++;
        G[i] = comp_id[r];
    }
    return G;
}

Compilation message (stderr)

sphinx.cpp:2:5: error: 'vector' does not name a type
    2 |     vector<int> p;
      |     ^~~~~~
sphinx.cpp: In constructor 'DSU::DSU(int)':
sphinx.cpp:3:17: error: class 'DSU' does not have any field named 'p'
    3 |     DSU(int n): p(n) { iota(p.begin(),p.end(),0); }
      |                 ^
sphinx.cpp:3:29: error: 'p' was not declared in this scope
    3 |     DSU(int n): p(n) { iota(p.begin(),p.end(),0); }
      |                             ^
sphinx.cpp:3:24: error: 'iota' was not declared in this scope
    3 |     DSU(int n): p(n) { iota(p.begin(),p.end(),0); }
      |                        ^~~~
sphinx.cpp: In member function 'int DSU::find(int)':
sphinx.cpp:4:29: error: 'p' was not declared in this scope
    4 |     int find(int x){ return p[x]==x?x:p[x]=find(p[x]); }
      |                             ^
sphinx.cpp: In member function 'void DSU::unite(int, int)':
sphinx.cpp:7:18: error: 'p' was not declared in this scope
    7 |         if(a!=b) p[b]=a;
      |                  ^
sphinx.cpp: At global scope:
sphinx.cpp:11:1: error: 'vector' does not name a type
   11 | vector<int> find_colours(int N, vector<int> X, vector<int> Y) {
      | ^~~~~~