Submission #1245377

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245377		Hamed_Ghaffari	Sphinx's Riddle (IOI24_sphinx)	C++20	28.50 / 100	128 ms	1188 KiB

sphinx

#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;

const int MXN = 250;

int n;
vector<int> g[MXN], G;

namespace comp_cnt {
    vector<int> E;
    bool vis[MXN];
    void dfs(int v) {
        vis[v] = 1;
        for(int u : g[v])
            if(!vis[u] && E[v]==E[u] && (E[v]!=-1 || G[v]==G[u]))
                dfs(u);
    }
    int get(vector<int> E) {
        comp_cnt::E = E;
        fill(vis, vis+n, 0);
        int res=0;
        for(int i=0; i<n; i++)
            if(!vis[i]) {
                dfs(i);
                res++;
            }
        return res;
    }
}

namespace component {
    int timer=-1;
    bool mark[MXN], vis[MXN];
    int find_leaf(int v) {
        vis[v] = 1;
        for(int u : g[v])
            if(!mark[u] && !vis[u])
                return find_leaf(u);
        return v;
    }
    void solve() {
        int cnt=0, v=-1;
        for(int i=0; i<n; i++)
            if(!mark[i]) {
                vis[i] = 0;
                v = i;
                cnt++;
            }
        if(cnt==1) {
            G[v] = ++timer;
            return;
        }
        v = find_leaf(v);
        mark[v] = 1;
        solve();
        mark[v] = 0;
        vector<int> E(n, -1);
        for(int v=0; v<n; v++)
            if(mark[v])
                E[v] = n;
        if(perform_experiment(E)==comp_cnt::get(E)) {
            G[v] = ++timer;
            return;
        }
        int l=-1, r=timer, mid;
        while(r-l>1) {
            mid = (l+r)>>1;
            for(int v=0; v<n; v++)
                if(!mark[v])
                    E[v] = (G[v]<=mid ? -1 : n);
            (perform_experiment(E)==comp_cnt::get(E) ? l : r) = mid;
        }
        G[v] = r;
    }
}

vector<int> find_colours(int N, vector<int> X, vector<int> Y) {
    n = N;
    G.resize(n, -1);
    for(int i=0; i<X.size(); i++)
        g[X[i]].push_back(Y[i]),
        g[Y[i]].push_back(X[i]);
    component::solve();
    return G;
}

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