Submission #217792

#	Time	Username	Problem	Language	Result	Execution time	Memory
217792		MarcoMeijer	Werewolf (IOI18_werewolf)	C++14	100 / 100	812 ms	129800 KiB

werewolf

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

//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define INF 1e9
#define pb push_back
#define fi first
#define se second
#define sz size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MX=5e5;

class RootedTree {
public:
	RootedTree() {
		RE(i,MX) p[i] = -1;
	}
	void addChild(int parent, int child) {
		chl[parent].pb(child);
		p[child] = parent;
	}
	void createA(int u) {
		a[m] = u;
		bg[u] = m++;
		for(int v:chl[u]) createA(v);
		ed[u] = m-1;
	}
	void createA() {
		createA(root);
	}

	vi chl[MX];
	int p[MX];
	int root;
	int a[MX], bg[MX], ed[MX];
	int m=0;
};

int m, q, n;
vi adj[MX];
vi atL[MX], atR[MX];
vi A, X, Y, S, E, L, R;
int p[MX], r[MX];
RootedTree treeH, treeW;
int SEG[MX*4];
int SA[MX];

int getSet(int i) {return i==p[i]?i:p[i]=getSet(p[i]);}
bool isSameSet(int i, int j) {return getSet(i)==getSet(j);}
void unionSet(int i, int j) {
	if(!isSameSet(i,j)) {
		i=getSet(i), j=getSet(j);
		p[j] = i;
	}
}

void setSeg(int i, int x, int p=0, int l=0, int r=n-1) {
	if(i < l || i > r) return;
	if(l == r) {
		SEG[p] = x;
		return;
	}
	int m=(l+r)/2;
	setSeg(i,x,p*2+1,l,m);
	setSeg(i,x,p*2+2,m+1,r);
	SEG[p] = max(SEG[p*2+1], SEG[p*2+2]);
}
int getSeg(int i, int j, int p=0, int l=0, int r=n-1) {
	if(j < l || i > r) return -1;
	if(i <= l && j >= r) return SEG[p];
	int m=(l+r)/2;
	int a=getSeg(i,j,p*2+1,l,m);
	int b=getSeg(i,j,p*2+2,m+1,r);
	return max(a,b);
}

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();
	L=_L, R=_R, X=_X, Y=_Y, S=_S, E=_E;
	A.assign(q, 0);
	RE(i,m) {
		adj[X[i]].pb(Y[i]);
		adj[Y[i]].pb(X[i]);
	}

	RE(i,q) {
		atL[L[i]].pb(i);
		atR[R[i]].pb(i);
	}

	RE(i,n) p[i]=i, r[i]=0;
	RE(i,n) {
		for(int j:adj[i]) {
			if(j > i || isSameSet(i,j)) continue;
			j = getSet(j);
			unionSet(i,j);
			treeW.addChild(i,j);
		}
		for(int j:atR[i]) E[j] = getSet(E[j]);
	}
	treeW.root = n-1;
	RE(i,n) p[i]=i, r[i]=0;
	REV(i,0,n) {
		for(int j:adj[i]) {
			if(j < i ||isSameSet(i,j)) continue;
			j = getSet(j);
			unionSet(i,j);
			treeH.addChild(i,j);
		}
		for(int j:atL[i]) S[j] = getSet(S[j]);
	}
	treeH.root = 0;
	treeW.createA();
	treeH.createA();

	viii queries;
	RE(curQ,q) {
		int bg, ed;
		int u = S[curQ];
		bg = treeH.bg[u];
		ed = treeH.ed[u];
		queries.pb(tie(ed,bg,curQ));
	}
	sort(queries.begin(), queries.end());
	RE(i,n*4) SEG[i] = -1;
	RE(i,n) SA[treeW.a[i]] = i;

	int j=0;
	for(iii p : queries) {
		int bg, ed, curQ;
		tie(ed, bg, curQ) = p;
		while(j <= ed) {
			setSeg(SA[treeH.a[j]],j);
			j++;
		}
		int u = E[curQ];
		if(getSeg(treeW.bg[u], treeW.ed[u]) >= bg) {
			A[curQ] = 1;
		} else {
			A[curQ] = 0;
		}
	}

	return A;
}

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