Submission #897222

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
897222	2024-01-02T18:15:46 Z	aqxa	Game (IOI14_game)	C++17	Compilation error	0 ms	0 KB

game

#include <bits/stdc++.h>
using namespace std;

using ll = long long; 

const int N = 1505; 

int a[N][N], cnt[N][N];
int _n;  
vector<int> e; 
int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
bool unite(int x, int y) {
	x = get(x); y = get(y); 
	if (x == y) return false; 
	if (e[x] > e[y]) swap(x, y); 
	e[x] += e[y]; e[y] = x; 
	for (int i = 0; i < _n; ++i) {
		if (e[i] < 0 && i != x && i != y) {
			cnt[min(x, i)][max(x, i)] += cnt[min(y, i)][max(y, i)]; 
		}
	}
	return true; 
}


void initialize(int n) {
	_n = n; 
	e = vector<int>(n, -1);

	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			cnt[i][j] = 1; 
		}
	}
}

int hasEdge(int u, int v) {
	u--; v--; 
	if (u > v) swap(u, v); 
	int cu = get(u), cv = get(v); 
	if (cu == cv) return 1; 
	if (cu > cv) swap(cu, cv); 

	if (cnt[cu][cv] == 1) {
		unite(cu, cv); 
		// int np = get(cu); 
		// for (int i = 0; i < _n; ++i) {
		// 	if (e[i] < 0 && i != cu && i != cv) {
		// 		cnt[min(i, np)][max(i, np)] = cnt[min(i, cu)][max(i, cu)] + cnt[min(i, cv)][max(i, cv)]; 
		// 	}
		// }
		return 1; 
	} else {
		cnt[cu][cv]--; 
		return 0; 
	}
}


mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll B) {
	return (unsigned long long)rng() % B;
}
 
int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t = 40; 
	int r = t * (t - 1) / 2; 
	vector<pair<int, int>> p; 
	for (int i = 1; i <= t; ++i) {
		for (int j = i + 1; j <= t; ++j) {
			p.push_back({i, j}); 
		}
	}
	
	int tt = 1000; 
	while (tt--) {
		random_shuffle(p.begin(), p.end()); 
		initialize(t); 
		string user_ans = ""; 
		for (auto [x, y]: p) {
			int v = hasEdge(x, y); 
			user_ans += (char) ('0' + v); 
		}
		vector<set<int>> st(t); 
		for (int i = 0; i < r - 1; ++i) {	
			if (user_ans[i] == '0') continue; 
			st[p[i].first - 1].insert(p[i].second - 1); 
			st[p[i].second - 1].insert(p[i].first - 1); 
		}
		int cc = 0; 
		vector<int> vis(t, 0); 
		function<void(int)> dfs = [&] (int x) {
			vis[x] = cc + 1; 
			for (auto u: st[x]) {
				if (vis[u] == 0) {
					dfs(u); 
				}
			}
		}; 
		for (int i = 0; i < t; ++i) {
			if (!vis[i]) {
				dfs(i); 
				cc++; 
			}
		}
		if (cc != 2 || vis[p[r - 1].first - 1] == vis[p[r - 1].second - 1]) {
			cout << cc << ' ' << vis[p[r - 1].first] << ' ' << vis[p[r - 1].second] << '\n';
			cout << "WA\n";
			cout << "User output: \n" << user_ans << "\n";
			cout << "Graph: \n";
			for (auto [x, y]: p) {
				cout << x << ' '<< y << '\n';
			}
		}
	} 

	return 0; 
}	

Compilation message

/usr/bin/ld: /tmp/ccl1ZPQX.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccAAhXkX.o:game.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status