Submission #1230386

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230386		PVM_pvm	Sphinx's Riddle (IOI24_sphinx)	C++20	28.50 / 100	98 ms	1236 KiB

sphinx

#include "sphinx.h"
#include<bits/stdc++.h>
using namespace std;
#define MAXN 252
int n;
int cvet[MAXN];
vector<int> v[MAXN];
bool b[MAXN];
vector<vector<int>> komp;
bool c2[MAXN];
void dfs2(int x)
{
    c2[x]=1;
    for (int q=0;q<v[x].size();q++)
    {
        if (c2[v[x][q]]) continue;
        if (cvet[ v[x][q] ]==-1) continue;
        dfs2(v[x][q]);
    }
}
bool check(int lf, int rt, int x)
{
    int ans=rt-lf+2;
    for (int q=0;q<n;q++) cvet[q]=n;
    cvet[x]=-1;
    for (int q=lf;q<=rt;q++)
    {
        for (int w=0;w<komp[q].size();w++) cvet[ komp[q][w] ]=-1;
    }
    vector<int> E(n,n);
    E[x]=-1;
    for (int q=lf;q<=rt;q++)
    {
        for (int w=0;w<komp[q].size();w++) E[ komp[q][w] ]=-1;
    }
    for (int q=0;q<n;q++) c2[q]=0;
    for (int q=0;q<n;q++)
    {
        if (c2[q]) continue;
        if (cvet[q]==-1) continue;
        ans++;
        dfs2(q);
    }
    int klk=perform_experiment(E);
    if (klk<ans) return true;
    return false;
}
void dfs(int x)
{
    b[x]=1;
    vector<int> moiko;
    int lft=0;
    while (true)
    {
        if (lft>=komp.size()) break;
        bool ch=check(lft,komp.size()-1,x);
        if (!ch) break;
        int l=lft-1,r=komp.size()-1;
        while (l<r-1)
        {
            int mid=(l+r)/2;
            ch=check(lft,mid,x);
            if (ch) r=mid;
            else l=mid;
        }
        moiko.push_back(r);
        lft=r+1;
    }
    if (moiko.size()==0)
    {
        vector<int> vvv(1,x);
        komp.push_back(vvv);
    }
    else if (moiko.size()==1)
    {
        komp[ moiko[0] ].push_back(x);
    }
    else
    {
        assert(0);
        komp[ moiko[0] ].push_back(x);
        for (int q=moiko.size()-1;q>0;q--)
        {
            for (int w=0;w<komp[ moiko[q] ].size();w++) komp[ moiko[0] ].push_back(komp[ moiko[q] ][w]);
            swap(komp[ moiko[q] ],komp[ komp.size()-1 ]);
            komp.pop_back();
        }
    }
    for (int q=0;q<v[x].size();q++)
    {
        if (b[v[x][q]]) continue;
        dfs(v[x][q]);
    }
}
vector<int> find_colours(int N, vector<int> X, vector<int> Y) {
    vector<int> G(N, -1);
    n=N;
    for (int q=0;q<X.size();q++)
    {
        v[X[q]].push_back(Y[q]);
        v[Y[q]].push_back(X[q]);
    }
    dfs(1);
    for (int q=0;q<komp.size();q++)
    {
        for (int w=0;w<komp[q].size();w++) G[komp[q][w]]=q;
    }
    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