제출 #1239605

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1239605		hengliao	Sphinx's Riddle (IOI24_sphinx)	C++20	24 / 100	31 ms	1172 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];
	bool visited[mxN];

	void dfs(ll cur, ll u, ll v){
		if(cur==u || cur==v || visited[cur]) return;
		visited[cur]=1;
		for(auto &it:adj[cur]){
			dfs(it, u, v);
		}
	}

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

	
}

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

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

	for(ll i=0;i<n;i++){
		ll lef=0, rig=n-2;
		ll good=-1;
		while(lef<=rig){
			ll mid=(lef+rig)/2;
			if(qry(i, mid)){
				good=mid;
				rig=mid-1;
			}
			else{
				lef=mid+1;
			}
		}
		if(good==-1){
			ans[i]=n-1;
		}
		else{
			ans[i]=good;
		}
	}

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

	return ans;
}

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