Submission #1239587

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239587		hengliao	Sphinx's Riddle (IOI24_sphinx)	C++20	10 / 100	391 ms	1176 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);
	for(ll i=0;i<n;i++){
		for(ll c=0;c<n;c++){
			vll tep(n, n);
			tep[i]=-1;
			tep[adj[i][0]]=c;
			if(perform_experiment(tep)==f(i, adj[i][0])+1){
				ans[i]=c;
				break;
			}
		}
	}

	return ans;
}

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