oj.uz

Submission #128974

# Submission time Handle Problem Language Result Execution time Memory
128974 2019-07-11T11:37:16 Z Kerim Werewolf (IOI18_werewolf) C++17
100 / 100
 1085 ms 119016 KB 
#include "werewolf.h"
#include "bits/stdc++.h"
#define MAXN 200009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int n,m,q,ata[MAXN];
int tap(int x){
	if(ata[x]==x)
		return x;
	return ata[x]=tap(ata[x]);	
}
vector<int>adj[MAXN][2],a[MAXN],b[MAXN];
int in[MAXN][2],out[MAXN][2],id[MAXN][2],P[MAXN][18][2],pos[MAXN],TIM;
void dfs(int nd,int t){
	in[nd][t]=++TIM;
	id[TIM][t]=nd;
	tr(it,adj[nd][t])
		dfs(*it,t);
	out[nd][t]=TIM;	
}
vector<pair<int,PII> >query[MAXN][2];
int F[MAXN];
void upd(int x){
	for(;x<MAXN;x+=x&(-x))
		F[x]++;	
}
int tap(int l,int r){l--;
	int res=0;
	for(;r;r-=r&(-r))
		res+=F[r];
	for(;l;l-=l&(-l))
		res-=F[l];
	return res;			
}
vector<int>check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E,vector<int> L, vector<int> R) {
	q=S.size();n=N;m=X.size();
	for(int i=0;i<m;i++){
		int u=X[i]+1,v=Y[i]+1;
		if(u>v)
			swap(u,v);
		a[u].pb(v);b[v].pb(u);
	}
	for(int i=1;i<=n;i++)
		ata[i]=i;
	for(int i=1;i<=n;i++)
		tr(it,b[i])
			if(tap(*it)!=i){
				adj[i][0].pb(tap(*it));
				P[tap(*it)][0][0]=i;
				ata[tap(*it)]=i;
			}	
	for(int i=1;i<=n;i++)
		ata[i]=i;
	for(int i=n;i>=1;i--)
		tr(it,a[i])
			if(tap(*it)!=i){
				adj[i][1].pb(tap(*it));
				P[tap(*it)][0][1]=i;
				ata[tap(*it)]=i;
			}	
	for(int h=0;h<2;h++)
		for(int j=1;j<=17;j++)
			for(int i=1;i<=n;i++)
				if(P[i][j-1][h])
					P[i][j][h]=P[P[i][j-1][h]][j-1][h];	
	vector<int>ans(q);	
	dfs(n,0);TIM=0;dfs(1,1);
	for(int i=1;i<=n;i++)
		pos[id[i][1]]=i;	
	for(int i=0;i<q;i++){
		int s=S[i]+1,e=E[i]+1,l=L[i]+1,r=R[i]+1;
		for(int j=17;j>=0;j--){
			if(P[s][j][1]>=l)
				s=P[s][j][1];
			if(P[e][j][0] and P[e][j][0]<=r)	
				e=P[e][j][0];
		}
		//while(par[s][1]>=l)
		//	s=par[s][1];
		//while(par[e][0] and par[e][0]<=r)
		//	e=par[e][0];	
		query[in[e][0]][0].pb(mp(i,mp(in[s][1],out[s][1])));
		query[out[e][0]][1].pb(mp(i,mp(in[s][1],out[s][1])));	
	}
	for(int i=1;i<=n;i++){
		tr(it,query[i][0])
			ans[it->ff]-=tap(it->ss.ff,it->ss.ss);
		upd(pos[id[i][0]]);		
		tr(it,query[i][1])
			ans[it->ff]+=tap(it->ss.ff,it->ss.ss);
	}
	for(int i=0;i<q;i++)
		umin(ans[i],1);
	return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 28664 KB Output is correct
2 Correct 28 ms 28664 KB Output is correct
3 Correct 28 ms 28664 KB Output is correct
4 Correct 27 ms 28664 KB Output is correct
5 Correct 28 ms 28536 KB Output is correct
6 Correct 28 ms 28536 KB Output is correct
7 Correct 27 ms 28536 KB Output is correct
8 Correct 28 ms 28536 KB Output is correct
9 Correct 28 ms 28664 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 28664 KB Output is correct
2 Correct 28 ms 28664 KB Output is correct
3 Correct 28 ms 28664 KB Output is correct
4 Correct 27 ms 28664 KB Output is correct
5 Correct 28 ms 28536 KB Output is correct
6 Correct 28 ms 28536 KB Output is correct
7 Correct 27 ms 28536 KB Output is correct
8 Correct 28 ms 28536 KB Output is correct
9 Correct 28 ms 28664 KB Output is correct
10 Correct 36 ms 29688 KB Output is correct
11 Correct 35 ms 29652 KB Output is correct
12 Correct 35 ms 29660 KB Output is correct
13 Correct 36 ms 29816 KB Output is correct
14 Correct 35 ms 29816 KB Output is correct
15 Correct 37 ms 29788 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 829 ms 98588 KB Output is correct
2 Correct 908 ms 101632 KB Output is correct
3 Correct 780 ms 107476 KB Output is correct
4 Correct 790 ms 106192 KB Output is correct
5 Correct 746 ms 106308 KB Output is correct
6 Correct 821 ms 106652 KB Output is correct
7 Correct 720 ms 105368 KB Output is correct
8 Correct 795 ms 110044 KB Output is correct
9 Correct 728 ms 107700 KB Output is correct
10 Correct 592 ms 105420 KB Output is correct
11 Correct 613 ms 106160 KB Output is correct
12 Correct 666 ms 105836 KB Output is correct
13 Correct 898 ms 118780 KB Output is correct
14 Correct 931 ms 118700 KB Output is correct
15 Correct 1085 ms 118696 KB Output is correct
16 Correct 974 ms 118732 KB Output is correct
17 Correct 817 ms 105304 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 28664 KB Output is correct
2 Correct 28 ms 28664 KB Output is correct
3 Correct 28 ms 28664 KB Output is correct
4 Correct 27 ms 28664 KB Output is correct
5 Correct 28 ms 28536 KB Output is correct
6 Correct 28 ms 28536 KB Output is correct
7 Correct 27 ms 28536 KB Output is correct
8 Correct 28 ms 28536 KB Output is correct
9 Correct 28 ms 28664 KB Output is correct
10 Correct 36 ms 29688 KB Output is correct
11 Correct 35 ms 29652 KB Output is correct
12 Correct 35 ms 29660 KB Output is correct
13 Correct 36 ms 29816 KB Output is correct
14 Correct 35 ms 29816 KB Output is correct
15 Correct 37 ms 29788 KB Output is correct
16 Correct 829 ms 98588 KB Output is correct
17 Correct 908 ms 101632 KB Output is correct
18 Correct 780 ms 107476 KB Output is correct
19 Correct 790 ms 106192 KB Output is correct
20 Correct 746 ms 106308 KB Output is correct
21 Correct 821 ms 106652 KB Output is correct
22 Correct 720 ms 105368 KB Output is correct
23 Correct 795 ms 110044 KB Output is correct
24 Correct 728 ms 107700 KB Output is correct
25 Correct 592 ms 105420 KB Output is correct
26 Correct 613 ms 106160 KB Output is correct
27 Correct 666 ms 105836 KB Output is correct
28 Correct 898 ms 118780 KB Output is correct
29 Correct 931 ms 118700 KB Output is correct
30 Correct 1085 ms 118696 KB Output is correct
31 Correct 974 ms 118732 KB Output is correct
32 Correct 817 ms 105304 KB Output is correct
33 Correct 896 ms 106764 KB Output is correct
34 Correct 375 ms 64296 KB Output is correct
35 Correct 976 ms 109960 KB Output is correct
36 Correct 936 ms 107816 KB Output is correct
37 Correct 942 ms 108900 KB Output is correct
38 Correct 893 ms 108420 KB Output is correct
39 Correct 929 ms 117412 KB Output is correct
40 Correct 1014 ms 116656 KB Output is correct
41 Correct 792 ms 106564 KB Output is correct
42 Correct 685 ms 106232 KB Output is correct
43 Correct 1025 ms 115832 KB Output is correct
44 Correct 859 ms 107996 KB Output is correct
45 Correct 821 ms 118028 KB Output is correct
46 Correct 846 ms 117732 KB Output is correct
47 Correct 920 ms 118816 KB Output is correct
48 Correct 981 ms 118656 KB Output is correct
49 Correct 949 ms 119016 KB Output is correct
50 Correct 949 ms 118612 KB Output is correct
51 Correct 950 ms 116464 KB Output is correct
52 Correct 936 ms 116292 KB Output is correct