Submission #1198240

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198240		dubabuba	Werewolf (IOI18_werewolf)	C++20	15 / 100	3512 ms	34608 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

#define ff first
#define ss second
#define MP make_pair


const int mxn = 3030;
int n, m, q;
int Hans[mxn], Wans[mxn];

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef bitset<mxn> bi;

bi hun[mxn], dog[mxn];
struct Tree {
	int anc[mxn * 2], cnt;
	vector<int> chi[mxn * 2];
	vector<int> query[mxn * 2];
	
	Tree() { memset(anc, -1, sizeof anc); }
	
	int ancestor(int u) { return anc[u] < 0 ? u : anc[u] = ancestor(anc[u]); }
	int unite(int u, int v) {
		u = ancestor(u);
		v = ancestor(v);
		if(u == v) return -1;
		
		anc[cnt] += anc[u];
		anc[cnt] += anc[v];
		anc[u] = cnt;
		anc[v] = cnt;
		chi[cnt].push_back(u);
		chi[cnt].push_back(v);
		return cnt++;
	}

	bi dfs(int u, bool flag) {
		if(u < n) {
			bi ret = 0;
			ret[u] = 1;

			if(flag) {
				for(int i : query[u])
					hun[i] = ret;
			}
			else {
				for(int i : query[u])
					dog[i] = ret;
			}
			return ret;
		}

		bi ret = 0;
		for(int v : chi[u])
			ret |= dfs(v, flag);
		
			if(flag) {
				for(int i : query[u])
					hun[i] = ret;
			}
			else {
				for(int i : query[u])
					dog[i] = ret;
			}
		return ret;
	}
};

Tree humans, wolves;
vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
	n = N;
	m = X.size();
	q = S.size();

	vector<pii> HQ[n];
	vector<pii> WQ[n];

	for(int i = 0; i < m; i++) {
		int mn = min(X[i], Y[i]);
		int mx = max(X[i], Y[i]);
		HQ[mn].push_back(MP(-1, mx));
		WQ[mx].push_back(MP(-1, mn));
	}

	for(int i = 0; i < q; i++) {
		int l = L[i], r = R[i];
		HQ[l].push_back(MP(i, S[i]));
		WQ[r].push_back(MP(i, E[i]));
	}

	// cout << "\nWolves\n";
	wolves.cnt = n;
	for(int u = 0; u < n; u++) {
		for(pii p : WQ[u]) {
			int i = p.ff;
			int v = p.ss;

			if(i == -1) {
				int a = wolves.unite(u, v);
				// cout << u << ' ' << v << " -> " << a << endl;
			}
			else {
				Wans[i] = wolves.ancestor(v);
				wolves.query[Wans[i]].push_back(i);
				// cout << "query " << i << ": " << u << ' ' << v << " = " << Wans[i] << endl;
			}
		}
	}


	// cout << "\nHumans\n";
	humans.cnt = n;
	for(int u = n - 1; u >= 0; u--) {
		for(pii p : HQ[u]) {
			int i = p.ff;
			int v = p.ss;

			if(i == -1) {
				int a = humans.unite(u, v);
				// cout << u << ' ' << v << " -> " << a << endl;
			}
			else {
				Hans[i] = humans.ancestor(v);
				humans.query[Hans[i]].push_back(i);
				// cout << "query " << i << ": " << u << ' ' << n - 1 << " = " << Hans[i] << endl;
			}
		}
	}

	bool vis[n * 2];
	memset(vis, 0, sizeof vis);
	for(int i = 0; i < n; i++) {
		int a = wolves.ancestor(i);
		if(!vis[a]) {
			wolves.dfs(a, 1);
		}
	}

	memset(vis, 0, sizeof vis);
	for(int i = 0; i < n; i++) {
		int a = humans.ancestor(i);
		if(!vis[a]) {
			humans.dfs(a, 0);
		}
	}

	vi ret;
	bi buba = 0;
	for(int i = 0; i < q; i++) {
		buba = hun[i] & dog[i];

		// cout << S[i] << " -> " << L[i] << ' ' << R[i] << ": ";
		// for(int k = 0; k < n; k++)
		// 	cout << hun[i][k];
		// cout << endl;

		// cout << E[i] << " -> " << L[i] << ' ' << R[i] << ": ";
		// for(int k = 0; k < n; k++)
		// 	cout << dog[i][k];
		// cout << endl;
		

		if(buba.count())
			ret.push_back(1);
		else
			ret.push_back(0);
		// cout << endl;
	}
	return ret;
}

/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4

*/

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51