Submission #308973

#	Time	Username	Problem	Language	Result	Execution time	Memory
308973		nafis_shifat	Werewolf (IOI18_werewolf)	C++14	100 / 100	784 ms	83920 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
#define pii pair<int,int>
#define f first
#define s second
using namespace std;
const int mxn = 2e5 + 2;
struct reachability_tree {
	int parent[mxn];
	int sz[mxn];
	int in[mxn],out[mxn],id[mxn];
	int pc[mxn];
	vector<int> g[mxn];
	vector<int> w[mxn];
	int T=0;

	void init(int n) {
		for(int i=0;i<=n;i++) {
			parent[i] = i;
			sz[i] = 1;
		}
	}

	int findrep(int u) {
		return parent[u] == u ? u : findrep(parent[u]);
	}

	void unite(int u,int v,int cst) {
		u=findrep(u);
		v=findrep(v);
		if(u == v) return;

		if(sz[u] > sz[v]) swap(u,v);

		parent[u] = v;
		sz[v] += sz[u];
		g[v].push_back(u);
		w[v].push_back(cst);
		pc[u] = cst;

	}
	void dfs(int u) {
		in[u] = ++T;
		id[T] = u;

		for(int v : g[u]) {
			dfs(v);
		}
		out[u] = T;
	}


	pii range(int u, int tm,bool f) {
		if(f)
		    while(parent[u] != u && pc[u] >= tm) u = parent[u];
		else 
			while(parent[u] != u && pc[u] <= tm) u = parent[u];

		int p;
		if(f) {
			p = upper_bound(w[u].begin(),w[u].end(),tm,[](int a,int b) {
				return a > b;
			}) - w[u].begin();
		} else {
			p = upper_bound(w[u].begin(),w[u].end(),tm) - w[u].begin();
		}
		

		if(p == 0) {
			return {in[u], in[u]};
		}

		int v = g[u][p-1];
		return {in[u],out[v]};
	}


} hum,wlf ;



int U[2*mxn],V[2*mxn];

struct BIT
{
	int bit[mxn];
	void init() {
		memset(bit,0,sizeof bit);
	}	

	void update(int p,int v) {
		if(p==0) return;
		for(;p<mxn;p+=p&-p) bit[p] += v;
	}
    int query(int p) {
    	int r=0;
    	for(;p>0;p-=p&-p) r+=bit[p];
        return r;
    }
} bt;

struct Query {
	int L1,R1,L2,R2;
	int v;
	int ind;

	Query(int a,int b,int c,int d,int i) : L1(a),R1(b),L2(c),R2(d),ind(i) {};
};

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 = X.size();
	for(int i = 0 ; i < m; i++) {
		U[i] = min(X[i],Y[i]), V[i] = max(X[i],Y[i]);
	}
	vector<int> p1,p2;
	for(int i = 0; i < m; i++) {
		p1.push_back(i); 
		p2.push_back(i);
	}

	sort(p1.begin(),p1.end(),[](int a,int b) {
		return U[a] > U[b];
	});

	sort(p2.begin(),p2.end(),[](int a,int b) {
		return V[a] < V[b];
	});

	hum.init(N);
	wlf.init(N);

	int  q = S.size();

	vector<int> res(q); 

	

	for(int i : p1) {
		hum.unite(U[i],V[i],U[i]);
	}

	for(int i : p2) {
		wlf.unite(U[i],V[i],V[i]);
	}

	for(int i = 0; i < N;i++) {
		if(hum.parent[i] == i) hum.dfs(i);
		if(wlf.parent[i] == i) wlf.dfs(i);
	}


	vector<Query> Q;

	vector<int> sp[mxn];
	vector<int> ep[mxn];

	

	for(int i = 0; i < q; i++) {
		pii x = hum.range(S[i],L[i],true);
		pii y = wlf.range(E[i],R[i],false);
		Q.push_back(Query(x.f,x.s,y.f,y.s,i));
		sp[x.f].push_back(i);
		ep[x.s].push_back(i);

	}

	bt.init();



	for(int i = 1 ; i <= N; i++ ) {
	
		for(int j : sp[i]) {
			Q[j].v = bt.query(Q[j].R2) - bt.query(Q[j].L2 - 1);
		}

		bt.update(wlf.in[hum.id[i]],1);
		for(int j : ep[i]) {
			int t = bt.query(Q[j].R2) - bt.query(Q[j].L2 - 1);
			if(t > Q[j].v) 
				res[j] = 1;
		}



	} 

	return res;




}

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