Submission #1245397

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245397		Hamed_Ghaffari	스핑크스 (IOI24_sphinx)	C++20	18 / 100	5 ms	500 KiB

sphinx

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

#define SZ(x) int(x.size())

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++;
            }
        // cout << res << '\n';
        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;
        }
        // cout << v << ' ';
        v = find_leaf(v);
        // cout << v << '\n';
        mark[v] = 1;
        solve();
        mark[v] = 0;
        // cout << "NOW " << v << '\n';
        vector<int> E(n, -1);
        for(int i=0; i<n; i++)
            if(mark[i])
                E[i] = n;
        if(perform_experiment(E)==comp_cnt::get(E)) {
            G[v] = ++timer;
            return;
        }
        vector<int> vec;
        for(int u : g[v])
            if(!mark[u])
                vec.push_back(u);

        int l=-1, r=SZ(vec)-1, mid;
        while(r-l>1) {
            mid = (l+r)>>1;
            for(int i=0; i<=mid; i++) E[vec[i]] = -1;
            for(int i=mid+1; i<n; i++) E[vec[i]] = n;
            (perform_experiment(E)==comp_cnt::get(E) ? l : r) = mid;
        }
        G[v] = G[vec[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: 0 / 21
• Subtask 5: 0 / 36