Submission #1230386

#TimeUsernameProblemLanguageResultExecution timeMemory
1230386PVM_pvmSphinx's Riddle (IOI24_sphinx)C++20
28.50 / 100
98 ms1236 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...