Submission #1239740

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239740		hengliao	Sphinx's Riddle (IOI24_sphinx)	C++20	100 / 100	868 ms	1464 KiB

sphinx

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

#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
#define pb push_back

typedef int ll;

namespace{
	
	const ll mxN=255;

	ll n, m;
	// vll adj[mxN];
	vll adj2[mxN];
	bool visited[mxN];
	bool done[mxN];
	vll tep, ans;
	ll timer;
	bool adj[mxN][mxN];
	vll ver[mxN];
	ll re[mxN];
	vll compadj[mxN];
	vll tree[mxN];
	ll d[mxN];
	vll dumb[2];
	
	// struct DSU{
	// 	ll dsu[mxN];

	// 	void init(){
	// 		memset(dsu, -1, sizeof(dsu));
	// 	}

	// 	ll find_set(ll tar){
	// 		if(dsu[tar]<0) return tar;
	// 		return dsu[tar]=find_set(dsu[tar])
	// 	}

	// 	void unite(ll a, ll b){
	// 		ll f=find_set(a);
	// 		ll s=find_set(b);
	// 		if(abs(dsu[f])<abs(dsu[s])) swap(f, s);
	// 		dsu[f]+=dsu[s];
	// 		dsu[s]=f;
	// 	}
	// };

	void dfs(ll cur, ll u){
		if(cur==u || visited[cur]) return;
		visited[cur]=1;
		for(ll i=0;i<n;i++){
			if(adj[cur][i]){
				if(tep[cur]==n && tep[i]==n){
					dfs(i, u);
				}
				else if(tep[cur]==-1 && tep[i]==-1 && ans[cur]==ans[i]){
					dfs(i, u);
				}
			}
		}
	}

	void dfs2(ll cur, ll a){
		if(done[cur]) return;
		done[cur]=1;
		ans[cur]=a;
		for(auto &it:adj2[cur]){
			dfs2(it, a);
		}
	}

	void dfs4(ll cur){
		if(visited[cur]) return;
		visited[cur]=1;
		for(ll i=0;i<n;i++){
			if(adj[cur][i]){
				if(tep[cur]!=-1 && tep[i]!=-1 && tep[cur]==tep[i]){
					dfs4(i);
				}
				// else if(tep[cur]==-1 && tep[i]==-1 && ans[cur]==ans[i]){
				// 	dfs(i, u);
				// }
			}
		}
	}

	void dfs5(ll cur, ll u){
		if(cur==u || visited[cur]) return;
		visited[cur]=1;
		for(ll i=0;i<n;i++){
			if(adj[cur][i]){
				if(tep[cur]==n && tep[i]==n){
					dfs5(i, u);
				}
				else if(tep[cur]!=-1 && tep[i]!=-1 && tep[cur]==tep[i]){
					dfs5(i, u);
				}
			}
		}
	}

	ll f(ll u){
		memset(visited, 0, sizeof(visited));
		ll cnt=0;
		for(ll i=0;i<n;i++){
			if(i==u) continue;
			if(!visited[i]){
				dfs(i, u);
				cnt++;
			}
		}
		return cnt;
	}

	ll f3(ll u){
		memset(visited, 0, sizeof(visited));
		ll cnt=0;
		for(ll i=0;i<n;i++){
			if(i==u) continue;
			if(!visited[i]){
				dfs5(i, u);
				cnt++;
			}
		}
		return cnt;
	}

	ll f2(){
		memset(visited, 0, sizeof(visited));
		ll cnt=0;
		for(ll i=0;i<n;i++){
			// if(i==u) continue;
			if(!visited[i] && tep[i]!=-1){
				dfs4(i);
				cnt++;
			}
		}
		return cnt;
	}

	ll ceil_div(ll a, ll b){
		return (a+b-1)/b;
	}

	void dfs3(ll cur, ll dep){
		if(visited[cur]) return;
		visited[cur]=1;
		d[cur]=dep;
		dumb[dep%2].pb(cur);
		for(auto &it:compadj[cur]){
			dfs3(it, dep+1);
		}
	}
	
}

vector<int> find_colours(int N, vector<int> X, vector<int> Y){
	memset(done, 0, sizeof(done));
	memset(adj, 0, sizeof(adj));
	memset(re, -1, sizeof(re));
	n=N;
	m=X.size();
	for(ll i=0;i<m;i++){
		adj[X[i]][Y[i]]=1;;
		adj[Y[i]][X[i]]=1;
	}
	ans=vll(n, -1);

	timer=0;

	auto qry=[&](ll u, ll tar){
		tep=vll(n, n);
		tep[u]=-1;
		for(ll i=u+1;i<n;i++){
			if(adj[u][i] && i<=tar && !done[i]){
				tep[i]=-1;
			}
		}
		if(perform_experiment(tep)==f(u)+1){
			return false;
		}
		return true;
	};

	for(ll i=n-1;i>=0;i--){
		memset(done, 0, sizeof(done));
		ans[i]=i;
		while(true){
			vll v;

			for(ll j=i+1;j<n;j++){
				if(adj[i][j] && !done[j]){
					v.pb(j);
				}
			}
			if(v.empty()) break;
			ll lef=0, rig=(ll) v.size()-1;
			ll good=-1;
			if(!qry(i, v[rig])){
				break;
			}
			while(lef<=rig){
				ll mid=(lef+rig)/2;
				if(qry(i, v[mid])){
					good=mid;
					rig=mid-1;
				}
				else{
					lef=mid+1;
				}
			}
			assert(good!=-1);
			dfs2(v[good], ans[i]);
			adj2[i].pb(v[good]);
			adj2[v[good]].pb(i);
		}
		
	}

	for(ll i=0;i<n;i++){
		ver[ans[i]].pb(i);
	}

	for(ll i=0;i<n;i++){
		for(ll j=i+1;j<n;j++){
			if(adj[i][j]){
				compadj[ans[i]].pb(ans[j]);
				compadj[ans[j]].pb(ans[i]);
			}
		}
	}



	for(ll i=0;i<n;i++){
		sort(compadj[i].begin(), compadj[i].end());
		compadj[i].erase(unique(compadj[i].begin(), compadj[i].end()), compadj[i].end());
	}



	memset(visited, 0, sizeof(visited));

	for(ll i=0;i<n;i++){
		if(!ver[i].empty() && !visited[i]){
			dfs3(i, 0);
		}
	}

	// for(ll i=0;i<n;i++){
	// 	if(!ver[i].empty()){
	// 		cout<<"comp: "<<i<<'\n';
	// 		cout<<"vertices: ";
	// 		for(auto &it:ver[i]){
	// 			cout<<it<<' ';
	// 		}
	// 		cout<<'\n';
	// 		cout<<"adj: ";
	// 		for(auto &it:compadj[i]){
	// 			cout<<it<<' ';
	// 		}
	// 		// cout<<'\n';
	// 		// cout<<"depth: "<<d[i]<<'\n';
	// 		// cout<<"_______\n";
	// 	}
	// }

	ll cc=0;
	for(ll i=0;i<n;i++){
		if(!ver[i].empty()) cc++;
	}

	if(cc==1){
		ll aa;
		for(ll c=0;c<n;c++){
			tep=vll(n, n);
			tep[0]=-1;
			ll tt;
			for(ll j=0;j<n;j++){
				if(adj[0][j]){
					tt=j;
					break;
				}
			}
			tep[tt]=c;
			if(perform_experiment(tep)==f3(0)){
				aa=c;
				break;
			}
		}
		vll ans2(n, aa);
		return ans2;
	}

	auto qry2=[&](ll c, ll tar, ll flag){
		// cout<<"qry2ing "<<c<<' '<<tar<<' '<<flag<<'\n';
		tep=vll(n, c);
		ll cntt=0;
		for(auto &it:dumb[flag]){
			if(it>tar || re[it]!=-1) continue;
			for(auto &it2:ver[it]){
				tep[it2]=-1;
			}
			cntt++;
		}
		ll tep2=perform_experiment(tep);
		ll tep3=f2()+cntt;
		if(tep2==tep3){
			// cout<<"values "<<tep2<<' '<<tep3<<'\n';
			// cout<<"return false\n";
			return false;
		}
		// cout<<"return true\n";
		return true;
	};

	for(ll i=0;i<2;i++){
		sort(dumb[i].begin(), dumb[i].end());
	}

	for(ll c=0;c<n;c++){
		for(ll i=0;i<2;i++){
			while(true){
				vll tep4;
				for(auto &it:dumb[i]){
					if(re[it]==-1){
						tep4.pb(it);
					}
				}
				if(tep4.empty()) break;
				ll lef=0, rig=(ll) tep4.size()-1;
				if(!qry2(c, tep4[rig], i)){
					break;
				}
				ll good=-1;
				while(lef<=rig){
					ll mid=(lef+rig)/2;
					if(qry2(c, tep4[mid], i)){
						good=mid;
						rig=mid-1;
					}
					else{
						lef=mid+1;
					}
				}
				re[tep4[good]]=c;
			}
		}
	}

	vll ans2(n);

	for(ll i=0;i<n;i++){
		ans2[i]=re[ans[i]];
	}
	// cout<<qry(1, 0)<<'\n';

	return ans2;
}

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