Submission #1239682

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239682		hengliao	Sphinx's Riddle (IOI24_sphinx)	C++20	50 / 100	699 ms	996 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];

	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);
		}
	}

	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 ceil_div(ll a, ll b){
		return (a+b-1)/b;
	}
	
}

vector<int> find_colours(int N, vector<int> X, vector<int> Y){
	memset(done, 0, sizeof(done));
	memset(adj, 0, sizeof(adj));
	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);
		}
		
	}

	// cout<<qry(1, 0)<<'\n';

	return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 1.5 / 3
• Subtask 2: 3.5 / 7
• Subtask 3: 16.5 / 33
• Subtask 4: 10.5 / 21
• Subtask 5: 18 / 36