oj.uz

Submission #261238

# Submission time Handle Problem Language Result Execution time Memory
261238 2020-08-11T15:14:58 Z medk Werewolf (IOI18_werewolf) C++14
100 / 100
 1206 ms 81648 KB 
#include <bits/stdc++.h>
#include "werewolf.h"

#define ll long long
#define pb push_back
#define x first
#define y second
#define sz(u) (int)(u.size())
#define all(u) u.begin(),u.end()

using namespace std;

int n,m,q,timer,root[2];
vector<vector<int>> g;
vector<vector<pair<int,int>>> tr[2];
vector<int> dsu,sz, in[2], out[2];
vector<pair<int,int>> par[2],trav[2];
vector<int> bit;

void upd(int x, int v){
	for(;x<=n;x+=x&-x) bit[x]+=v;
}

int sum(int x){
	int ret=0;
	for(;x>0;x-=x&-x) ret+=bit[x];
	return ret;
}

int getp(int x){
	return dsu[x]==x?x:dsu[x]=getp(dsu[x]);
}

void connect(int u, int v, int t){
	u=getp(u), v=getp(v);
	if(u==v) return;
	if(sz[u]<sz[v]) swap(u,v);
	dsu[v]=u;
	sz[u]+=sz[v];
	par[t][v]={timer,u};
	tr[t][u].pb({timer,v});
}

bool connected(int u, int v){
	return getp(u)==getp(v);
}

void dfs(int u, int t){
	in[t][u]=sz(trav[t]);
	trav[t].pb({u,in[t][u]});
	for(auto v:tr[t][u]){
		dfs(v.y,t);
	}
	out[t][u]=sz(trav[t])-1;
}

pair<int,int> getblock(int u, int L, int t){
	while(par[t][u].x<=L) u = par[t][u].y;
	int l=-1, r=sz(tr[t][u])-1;
	while(l<r){
		int md=(l+r+1)/2;
		if(tr[t][u][md].x>L) r=md-1;
		else l=md;
	}
	if(l==-1) return {in[t][u],in[t][u]};
	return {in[t][u],out[t][tr[t][u][l].y]};
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
	n=N;
	m=sz(X);
	q=sz(S);
	g.resize(n), dsu.resize(n), sz.resize(n), tr[0].resize(n), tr[1].resize(n), par[0].resize(n), par[1].resize(n);
	in[0].resize(n), in[1].resize(n), out[0].resize(n), out[1].resize(n), bit.resize(n+1);
	for(int i=0;i<n;i++) dsu[i]=i, sz[i]=1, par[0][i]=par[1][i]={(int)1e9,-1};
	for(int i=0;i<m;i++){
		g[X[i]].pb(Y[i]);	
		g[Y[i]].pb(X[i]);	
	}
	for(int i=0;i<n;i++) sort(all(g[i]));
	for(int i=0;i<n;i++){
		timer=i;
		for(int u:g[i]){
			if(i<u) continue;
			connect(i,u,0);
		}
	}
	root[0]=getp(0);
	dfs(root[0],0);
	for(int i=0;i<n;i++) dsu[i]=i, sz[i]=1;
	for(int i=n-1;i>=0;i--){
		timer=n-1-i;
		for(int u:g[i]){
			if(i<u) connect(i,u,1);
		}
	}
	root[1]=getp(0);
	dfs(root[1],1);
	sort(all(trav[0]));
	sort(all(trav[1]));
	for(int i=0;i<n;i++) trav[1][i].x=trav[0][i].y, swap(trav[1][i].x,trav[1][i].y);
	sort(all(trav[1]));
	vector<pair<pair<int,int>,int>> queriesL[n], queriesR[n];
	vector<int> cnt(q);
	for(int i=0;i<q;i++){
		pair<int,int> p1=getblock(E[i],R[i],0);
		pair<int,int> p2=getblock(S[i],n-1-L[i],1);
		if(p2.x>0 && p1.x>0) queriesL[p2.x-1].pb({{p1.x-1,i},-1});
		if(p1.x>0) queriesL[p2.y].pb({{p1.x-1,i},1});
		if(p2.x>0 && p1.y<n-1) queriesR[p2.x-1].pb({{p1.y+1,i},-1});
		if(p1.y<n-1) queriesR[p2.y].pb({{p1.y+1,i},1});
		cnt[i]=p2.y-p2.x+1;
	}
	for(int i=0;i<n;i++){
		upd(trav[1][i].y+1,1);
		for(auto p:queriesL[i]){
			cnt[p.x.y]-=sum(p.x.x+1)*p.y; 
		}
	}
	for(int i=0;i<=n;i++) bit[i]=0;
	for(int i=0;i<n;i++){
		upd(trav[1][i].y+1,1);
		for(auto p:queriesR[i]){
			cnt[p.x.y]-=(sum(n)-sum(p.x.x))*p.y; 
		}
	}
	vector<int> ret(q);
	for(int i=0;i<q;i++) ret[i]=(bool)(cnt[i]>0);
	return ret;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 11 ms 1408 KB Output is correct
11 Correct 8 ms 1408 KB Output is correct
12 Correct 13 ms 1536 KB Output is correct
13 Correct 7 ms 1408 KB Output is correct
14 Correct 7 ms 1408 KB Output is correct
15 Correct 8 ms 1536 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1206 ms 74148 KB Output is correct
2 Correct 751 ms 70368 KB Output is correct
3 Correct 682 ms 70472 KB Output is correct
4 Correct 810 ms 71752 KB Output is correct
5 Correct 852 ms 72648 KB Output is correct
6 Correct 1133 ms 77436 KB Output is correct
7 Correct 954 ms 77752 KB Output is correct
8 Correct 641 ms 70360 KB Output is correct
9 Correct 592 ms 72292 KB Output is correct
10 Correct 618 ms 73296 KB Output is correct
11 Correct 603 ms 73560 KB Output is correct
12 Correct 635 ms 75204 KB Output is correct
13 Correct 809 ms 72796 KB Output is correct
14 Correct 832 ms 72648 KB Output is correct
15 Correct 821 ms 72608 KB Output is correct
16 Correct 840 ms 72800 KB Output is correct
17 Correct 951 ms 77280 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 11 ms 1408 KB Output is correct
11 Correct 8 ms 1408 KB Output is correct
12 Correct 13 ms 1536 KB Output is correct
13 Correct 7 ms 1408 KB Output is correct
14 Correct 7 ms 1408 KB Output is correct
15 Correct 8 ms 1536 KB Output is correct
16 Correct 1206 ms 74148 KB Output is correct
17 Correct 751 ms 70368 KB Output is correct
18 Correct 682 ms 70472 KB Output is correct
19 Correct 810 ms 71752 KB Output is correct
20 Correct 852 ms 72648 KB Output is correct
21 Correct 1133 ms 77436 KB Output is correct
22 Correct 954 ms 77752 KB Output is correct
23 Correct 641 ms 70360 KB Output is correct
24 Correct 592 ms 72292 KB Output is correct
25 Correct 618 ms 73296 KB Output is correct
26 Correct 603 ms 73560 KB Output is correct
27 Correct 635 ms 75204 KB Output is correct
28 Correct 809 ms 72796 KB Output is correct
29 Correct 832 ms 72648 KB Output is correct
30 Correct 821 ms 72608 KB Output is correct
31 Correct 840 ms 72800 KB Output is correct
32 Correct 951 ms 77280 KB Output is correct
33 Correct 1111 ms 79156 KB Output is correct
34 Correct 411 ms 35576 KB Output is correct
35 Correct 1002 ms 75096 KB Output is correct
36 Correct 1054 ms 79796 KB Output is correct
37 Correct 951 ms 75652 KB Output is correct
38 Correct 1006 ms 78376 KB Output is correct
39 Correct 796 ms 73728 KB Output is correct
40 Correct 942 ms 81648 KB Output is correct
41 Correct 826 ms 74432 KB Output is correct
42 Correct 682 ms 73416 KB Output is correct
43 Correct 908 ms 74336 KB Output is correct
44 Correct 799 ms 74728 KB Output is correct
45 Correct 638 ms 71588 KB Output is correct
46 Correct 686 ms 69760 KB Output is correct
47 Correct 775 ms 72928 KB Output is correct
48 Correct 749 ms 72784 KB Output is correct
49 Correct 885 ms 73008 KB Output is correct
50 Correct 888 ms 72788 KB Output is correct
51 Correct 810 ms 81440 KB Output is correct
52 Correct 798 ms 79924 KB Output is correct