Submission #294028

#	Time	Username	Problem	Language	Result	Execution time	Memory
294028		amoo_safar	Werewolf (IOI18_werewolf)	C++17	15 / 100	4067 ms	74432 KiB

werewolf

#include "werewolf.h"

#include <bits/stdc++.h>


#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 2e5 + 10;

int par[N], pos[N];
vector<int> C[N];
int Find(int u){
	if(par[u] == u) return u;
	return par[u] = Find(par[u]);
}
void Unite(int u, int v){
	u = Find(u);
	v = Find(v);
	if(u == v) return ;
	if(C[u].size() < C[v].size()) swap(u, v);
	par[v] = u;
	for(auto x : C[v]){
		pos[x] = C[u].size();
		C[u].pb(x);
	}
	C[v].clear();
}
int n;
vi G[N];

pii res[N], s1[N], s2[N];
vector<pii> Q[N];

vi dsuArray(vi ord){
	vi mk(n, 0);
	for(int i : ord){
		par[i] = i;
		C[i] = {i};
		pos[i] = 0;
		for(int adj : G[i])
			if(mk[adj]) Unite(adj, i);
		
		for(auto X : Q[i]){
			res[X.S] = {-pos[X.F], C[Find(X.F)].size() - pos[X.F]};
		}
		
		mk[i] = 1;
	}
	return C[Find(0)];
}
vi DR, DL;
vi check_validity(int _n, vi X, vi Y, vi S, vi E, vi L, vi R){
	n = _n;
	int m = X.size();
	int q = S.size();

	for(int i = 0; i < m; i++) G[X[i]].pb(Y[i]), G[Y[i]].pb(X[i]);

	vi O;
	for(int i = 0; i < n; i++) O.pb(i);
	for(int i = 0; i < n; i++) Q[i].clear();
	for(int i = 0; i < q; i++) Q[R[i]].pb({E[i], i});
	DR = dsuArray(O);
	for(int i = 0; i < q; i++) s1[i] = {res[i].F + pos[E[i]], res[i].S + pos[E[i]]};

	
	reverse(all(O));
	for(int i = 0; i < n; i++) Q[i].clear();
	for(int i = 0; i < q; i++) Q[L[i]].pb({S[i], i});
	DL = dsuArray(O);
	for(int i = 0; i < q; i++) s2[i] = {res[i].F + pos[S[i]], res[i].S + pos[S[i]]};

	//cerr << "! ";
	//for(auto x : DR) cerr << x << ' ';
	//cerr << '\n';
	//for(int i = 0; i < q; i++) cerr << "# " << s1[i].F << ' ' << s1[i].S << '\n';


	vi ans;
	for(int i = 0; i < q; i++){
		bool fl = false;
		for(int j = s1[i].F; j < s1[i].S; j++)
			for(int k = s2[i].F; k < s2[i].S; k++)
				fl |= (DR[j] == DL[k]);
		ans.pb(fl);
	}
	return ans;
}

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