| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1117915 | nai0610 | Sphinx's Riddle (IOI24_sphinx) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll int64_t
#define ld long double
using namespace std;
//
const int maxn =1e5+5;
const int mod = 1e9+7; // 998244353,1610612741
const ll inf = 1e18;
const ld pi = atan(1.0L)*4;
struct Dsu{
vector<int> par;
void init(int n){
par.resize(n+5,0);
for (int i=1;i<=n;i++) par[i]=i;
}
int find (int v){
if (par[v]==v) return v;
return par[v]=find(par[v]);
}
bool join(int u,int v){
if ((u = find(u))==(v=find(v))) return false;
par[v]=u;
return true;
}
} dsu;
vector<int> find_colours(int n,vector<int> x,vector<int> y) {
dsu.init(n);
vector<vector<int>> g(n);
for (int i=0;i<x.size();i++) g[y[i]].push_back(x[i]);
auto nai =[&](vector<int> v,int c) {
int res=count(v.begin(),v.end(),c);
Dsu cnt;cnt.init(n);
for (int i=0;i<x.size();i++) {
if (v[x[i]]==c&&v[y[i]]==c) res-=cnt.join(x[i],y[i]);
}
return res;
};
for (int i=0;i<n;i++) {
map<int,int> m;
for (auto j:g[i]) m[dsu.find(j)]=j;
if (m.size()==0) continue;
vector<int> v;
for (auto j:m) v.push_back(j.second);
auto f =[&](int l,int r){
vector<int> u={i};
for (int j=l;j<r;j++) u.push_back(v[j]);
vector<int> w(n,n);
for (auto j:u) w[j]=-1;
return perform_experiment(w)-nai(w,n);
};
for (int j=0;j<v.size();j++) {
if (f(j,v.size())==v.size()-j+1) break;
int l=j,r=v.size();
while (l<=r) {
int mid = (l+r)/2;
if (f(j,mid)==mid-j+1) l=mid+1;
else r=mid-1;
}
dsu.join(v[l-1],i);
j=l;
}
}
vector<vector<int>> adj(n);
for (int i=0;i<x.size();i++) {
int u =dsu.find(x[i]);
int v =dsu.find(y[i]);
if (u!=v) {
adj[u].push_back(v);
adj[v].push_back(u);
}
}
vector<vector<int>> comp(n);
for (int i=0;i<n;i++) comp[dsu.find(i)].push_back(i);
int r=dsu.find(0);
vector<int> ord[2];
vector<int> h(n),vs(n);
queue<int> q;
q.push(r);
vs[r]=1;
while (!q.empty()) {
int u= q.front();q.pop();
ord[h[u]%2].push_back(u);
for (auto v:adj[u]){
if (!vs[v]) {
vs[v]=1;
h[v]=h[u]+1;
q.push(v);
}
}
}
vector<int> res(n,0);
if (comp[r].size()==n) {
for (int i=0;i<n;i++) {
vector<int> v(n,i);
v[0]=-1;
if (perform_experiment(v)==1) {
for (auto j:comp[r]) res[j]=i;
break;
}
}
return res;
}
for (int i=0;i<2;i++) {
auto f =[&](int c,int l,int r){
vector<int> v(n,c);
for (int j=0;j<n;j++) {
if (!comp[j].empty()&&h[j]%2==i) {
for (auto k:comp[j]) v[k]=n;
}
}
for (int j=l;j<r;j++) {
for (auto k:comp[ord[i][j]]) v[k]=-1;
}
return perform_experiment(v)-nai(v,c)-nai(v,n)<(r-l);
};
for (int j=1;j<n;j++) {
vector<int> a;
for (int k=0;k<ord[i].size();) {
if (!(f(j,k,ord[i].size()))) break;
int l=k,r=ord[i].size();
while (l<=r) {
int mid =(l+r)/2;
if (f(j,k,mid)==mid-k+1) l=mid+1;
else r=mid-1;
}
for (auto u:comp[ord[i][l-1]]) res[u]=j;
a.push_back(l-1);
k=l;
}
reverse(a.begin(),a.end());
for (auto x:a) ord[i].erase(ord[i].begin()+x);
}
}
return res;
}