Submission #130606

#	Time	Username	Problem	Language	Result	Execution time	Memory
130606		sealnot123	Werewolf (IOI18_werewolf)	C++14	100 / 100	875 ms	125848 KiB

werewolf

#include "werewolf.h"

#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define SZ(a) (int)(a).size()
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
typedef double D;
typedef long double LD;
typedef vector<int> VI;
const int N = 200005, Q = 400005;
int n, q, m;
struct A{
	int q, u, t;
	bool operator <(const A& o) const{
		return t<o.t;
	}
};

vector<int> g[N], G[N], ans;
vector<A> H, WW;
int P[Q], sz[Q], ll[Q], rr[Q], p[N], dp[N], T;
int st[N], en[N];
set<int> node[N];
set<int>::iterator IT;

int fin(int i){
	if(p[i]==i) return i;
	return fin(p[i]);
}

void merg(int a, int b, bool ww){
	a = fin(a); b = fin(b);
	if(a == b) return ;
	if(dp[a]<dp[b]) swap(a,b);
	if(!ww) G[a].pb(b);
	else{
		for(int it : node[b]) node[a].insert(it);
	}
	p[b] = a;
	dp[a] += dp[b];
}

void dfs(int u){
	st[u] = ++T;
	for(int e : G[u]) dfs(e);
	en[u] = T;
}

VI check_validity(int nn, VI X, VI Y, VI S, VI E, VI L, VI R) {
 	q = SZ(S);
 	n = nn;
 	m = SZ(X);
 	ans.resize(q);
 	int i,j,k,l,a,b,c,d;
 	for(i=0;i<m;i++){
 		g[X[i]].pb(Y[i]);
 		g[Y[i]].pb(X[i]);
 	}
 	for(i=0;i<q;i++){
 		H.pb({i, S[i], L[i]});
 		WW.pb({i, E[i], R[i]});
 	}
 	sort(all(H)); sort(all(WW));
 	// human preparation
 	int nw;
 	nw = q-1;
 	for(i=0;i<n;i++) p[i]=i, dp[i]=1;
 	for(i=n-1;i>=0;i--){
 		for(int e : g[i]){
 			if(e > i) merg(i,e,false);
 		}
 		while(nw>=0 && H[nw].t == i){
 			a = fin(H[nw].u);
 			b = H[nw].q;
 			P[b] = a; 
 			sz[b] = dp[a]; 
 			nw--;
 		}
 	}
 	for(i=0;i<n;i++){
 		if(p[i]==i) dfs(i);
 	}
 	for(i=0;i<q;i++){
 		ll[i] = st[P[i]];
 		rr[i] = st[P[i]]+sz[i]-1;
 	}
 	// werewolf prepareation
 	nw=0;
 	for(i=0;i<n;i++){
 		p[i] = i; dp[i] = 1;
 		node[i].insert(st[i]);
 	}
 	for(i=0;i<n;i++){
 		for(int e : g[i]){
 			if(e < i) merg(i, e, true);
 		}
 		while(nw<q && WW[nw].t == i){
 			a = fin(WW[nw].u);
 			b = WW[nw].q;
 			IT = node[a].lower_bound(ll[b]);
 			if(IT != node[a].end() && *IT <= rr[b]) ans[b] = 1;		
 			nw++;
 		}
 	}
  	return ans;
}
/*
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
*/

Compilation message (stderr)

werewolf.cpp: In function 'VI check_validity(int, VI, VI, VI, VI, VI, VI)':
werewolf.cpp:61:9: warning: unused variable 'j' [-Wunused-variable]
   int i,j,k,l,a,b,c,d;
         ^
werewolf.cpp:61:11: warning: unused variable 'k' [-Wunused-variable]
   int i,j,k,l,a,b,c,d;
           ^
werewolf.cpp:61:13: warning: unused variable 'l' [-Wunused-variable]
   int i,j,k,l,a,b,c,d;
             ^
werewolf.cpp:61:19: warning: unused variable 'c' [-Wunused-variable]
   int i,j,k,l,a,b,c,d;
                   ^
werewolf.cpp:61:21: warning: unused variable 'd' [-Wunused-variable]
   int i,j,k,l,a,b,c,d;
                     ^

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