Submission #1177418

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177418		Kaztaev_Alisher	Sphinx's Riddle (IOI24_sphinx)	C++20	1.50 / 100	3 ms	5104 KiB

sphinx

#include <bits/stdc++.h>

#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define all(a) a.begin() , a.end()
#define F first
#define S second

using namespace std;
using ll = long long;

const ll N = 2e5+5 , inf = 2e9 + 7;
const ll INF = 1e18 ,   mod = 1e9+7;

int perform_experiment(vector<int> E);

int n , was[N];
vector<int> g[N];
vector<int> G;
void get(int a , int b){
	vector<int> E(n , n);
	E[a] = -1; E[b] = -1;
	int y = perform_experiment(E);
	E[a] = 0; E[b] = 1;
	int x = perform_experiment(E);
	
	if(x != y){
		if(G[a] != -1){
			G[b] = G[a];
			return;
		}
		for(int i = 0; i < n; i++){
			vector<int> E(n, n);
			E[a] = i;
			E[b] = -1;
			int x = perform_experiment(E);
			if(x == y){
				G[a] = G[b] = i;
				return;
			}
		}
	} else {
		for(int i = 0; i < n; i++){
			vector<int> E(n, n);
			E[a] = i;
			E[b] = -1;
			int x = perform_experiment(E);
			if(x == y){
				G[b] = i;
				return;
			}
		}
	}
}
void dfs(int v, int p){
	was[v] = 1;
	for(int to : g[v]){
		if(G[to] == -1) get(v,to);
		if(G[v] == -1) get(to,v);
		if(was[to] == 0) dfs(to,v);
	}
}
vector<int> find_colours(int N, vector<int> X, vector<int> Y) {
	n = N;
	for(int i = 1; i <= n; i++) G.push_back(-1);
	for(int i = 0; i < X.size(); i++){		
		g[X[i]].push_back(Y[i]);
		g[Y[i]].push_back(X[i]);
	}
	for(int i = 0; i < n; i++){
		if(was[i] == 0){
			dfs(i,-1);
		}
	}
	
	return G;
}

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