Submission #1177606

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177606		Kaztaev_Alisher	Sphinx's Riddle (IOI24_sphinx)	C++20	0 / 100	2 ms	5128 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] , check[N] , p[N];
vector<int> g[N] , ord;
int gett(int x){
	if(p[x] == x) return x;
	return p[x] = gett(p[x]);
}
int merge(int a, int b){
	a = gett(a);
	b = gett(b);
	if(a == b) return 0 ;
	p[a] = b;
	return 1;
}
void dfs(int x) {
  was[x] = true;
  for (int i : g[x]) {
    if (!was[i] && ord[x] == ord[i]) dfs(i);
  }
}

int expected(int n) {
  for (int i = 0; i < n; i++) was[i] = false;

  int sum = 0;
  for (int i = 0; i < n; i++) {
    if (ord[i] == -1) {
      sum++;
    } else if (!was[i]) {
      sum++;
      dfs(i);
    }
  }

  return sum;
}
vector<int> find_colours(int N, vector<int> X, vector<int> Y) {
	n = N;
	ord.resize(n);
	for(int i = 0; i < n; i++) p[i] = i;
	for(int i = 0; i < X.size(); i++){		
		g[X[i]].push_back(Y[i]);
		g[Y[i]].push_back(X[i]);
	}
	for(int v = 0; v < n; v++){
		for(int i = 0; i < n; i++) check[i] = 0;
		for(int to : g[v]){
			if(to > v) continue;
			if(gett(v) == gett(to) || check[gett(to)]) continue;
			for(int i = 0; i < n; i++) ord[i] = n;
			ord[v] = -1; ord[to] = -1;
			int x = perform_experiment(ord);
			if(x == expected(n)) merge(v,to);
			else check[gett(to)] = 1;
		}
	}
	vector<int> G;
	for(int i = 0; i < n; i++) G.push_back(gett(p[i]));
	return G;
}
	

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