Submission #1196283

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196283		Muhammet	Werewolf (IOI18_werewolf)	C++20	15 / 100	4094 ms	103072 KiB

werewolf

#include "bits/stdc++.h"
#include "werewolf.h"
// #include "grader.cpp"

using namespace std;

#define SZ(s) (int)s.size()

const int N = 2e5 + 5;

vector <int> v[N], h[N], w[N], ph[N], pw[N], p;

int fnd(int x) {
	if(p[x] == x) return x;
	return p[x] = fnd(p[x]);
}

vector <int> check_validity(int n, vector <int> x, vector <int> y, vector <int> S,
 									vector <int> E, vector <int> L, vector <int> R) {
	int m = SZ(x), q = SZ(S);
	for(int i = 0; i < m; i++) {
		v[x[i]].push_back(y[i]);
		v[y[i]].push_back(x[i]);
	}
	vector <int> vis(n, 0);
	vector <vector <int>> sph(n, vector <int> (25, 0)), spw(n, vector <int> (25, 0));
	p.resize(n);
	for(int i = 0; i < n; i++) {
		p[i] = i, sph[i][0] = i;
	}
	for(int i = n-1; i >= 0; i--) {
		vis[i] = true;
		for(auto j : v[i]) {
			if(!vis[j]) continue;
			int k = fnd(j);
			if(k == i) continue;
			p[k] = i;
			sph[k][0] = i;
			h[i].push_back(k);
			// h[k].push_back(i);
		}
	}
	vis.assign(n, 0);
	for(int i = 0; i < n; i++) {
		p[i] = i, spw[i][0] = i;
	}
	for(int i = 0; i < n; i++) {
		vis[i] = true;
		for(auto j : v[i]) {
			if(!vis[j]) continue;
			int k = fnd(j);
			if(k == i) continue;
			p[k] = i;
			spw[k][0] = i;
			w[i].push_back(k);
			// w[k].push_back(i);
		}
	}
	for(int j = 1; j < 25; j++) {
		for(int i = 0; i < n; i++) {
			sph[i][j] = sph[sph[i][j-1]][j-1];
			spw[i][j] = spw[spw[i][j-1]][j-1];
		}
	}
	vector <int> ans;
	for(int i1 = 0; i1 < q; i1++) {
		int s = S[i1], e = E[i1], l = L[i1], r = R[i1];
		for(int i = 24; i >= 0; i--) {
			if(sph[s][i] >= l) s = sph[s][i];
			if(spw[e][i] <= r) e = spw[e][i];
		}
		vis.assign(n, 0);
		queue <int> q;
		q.push(s);
		while(!q.empty()) {
			int k = q.front();
			q.pop();
			vis[k] = true;
			for(auto i : h[k]) {
				q.push(i);
			} 
		}
		q.push(e);
		int tr = 0;
		while(!q.empty()) {
			int k = q.front();
			q.pop();
			if(vis[k]) tr = 1;
			for(auto i : w[k]) {
				q.push(i);
			} 
		}
		ans.push_back(tr);
	}
	return ans;
}

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