oj.uz

Submission #286164

# Submission time Handle Problem Language Result Execution time Memory
286164 2020-08-30T07:43:35 Z dvdg6566 Werewolf (IOI18_werewolf) C++14
100 / 100
 1157 ms 118360 KB 
#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
typedef long double ld;
#define pb emplace_back
#define mp make_pair
#define f first
#define s second
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define lb lower_bound
#define ub upper_bound
const int MAXN=200001;
const ll MOD=1e9+7;
const ll INF = 1e9;
const int MAXL = 18;

vpi edges;
vector<vi> V[2];
vi pre[2];
vi ipre[2];
vi post[2];
vi ord;
int p[MAXN][MAXL][2];

int up[MAXN];
int par(int x){return(up[x]==x)?x:up[x] = par(up[x]);}
int gx;
int N;

void dfs(int x,int pa,int a){
	pre[a][x]=gx;
	ipre[a][gx]=x;
	++gx;
	p[x][0][a] = pa;
	for(int i=1;i<MAXL;++i){
		if(p[x][i-1][a] == -1)continue;
		int b=p[x][i-1][a];
		p[x][i][a] = p[b][i-1][a];
	}

	for(auto t:V[a][x])if(t!=pa)dfs(t,x,a);
	post[a][x]=gx-1;
}

void generate_tree(int a){
	for(int i=0;i<N;++i){
		up[i]=i;
	}
	pre[a].resize(N,0);
	ipre[a].resize(N,0);
	post[a].resize(N,0);

	V[a].resize(N);
	gx=0;
	for(auto i:edges){
		if(par(i.f) == par(i.s))continue;
		i.s=par(i.s);
		assert(up[i.f] == i.f);
		if(a==0)assert(i.f>i.s);
		else assert(i.f<i.s);
		V[a][i.f].pb(i.s);
		up[i.s]=par(i.f);
	}
	if(a==0)dfs(N-1,-1,a);
	else dfs(0,-1,a);
}

bool B[MAXN];

typedef pair<pi,pi> pp;
vector<pp> sweep[MAXN]; // V[preA] = {index, postA, preB, postB}

struct node{
	int s,e,m,v;
	node *l,*r;
	node(int _s,int _e):s(_s),e(_e){
		m=(s+e)/2;
		v=1e9;
		if(s!=e){
			l=new node(s,m);r=new node(m+1,e);
		}
	}
	void up(int x,int va){
		if(s==e){v=va;return;}
		if(x<=m)l->up(x,va);
		else r->up(x,va);
		v=min(l->v,r->v);
	}
	int rmin(int x,int y){
		if(s==x&&e==y)return v;
		if(y<=m)return l->rmin(x,y);
		else if (x>m)return r->rmin(x,y);
		return min(l->rmin(x,m),r->rmin(m+1,y));
	}
}*root;

std::vector<int> check_validity(int _N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
  	N=_N;
  	memset(p,-1,sizeof(p));
  	for(int i=0;i<SZ(X);++i){
  		if(Y[i] > X[i])swap(X[i],Y[i]);
  		edges.pb(X[i],Y[i]);
  	}
  	sort(ALL(edges));
  	for(int i=0;i<N;++i)ord.pb(i);
  	generate_tree(0);


  	for(auto &i:edges)swap(i.f,i.s);
  	sort(ALL(edges));reverse(ALL(edges));
  	generate_tree(1);
  	// for(int i=0;i<N;++i)cout<<pre[1][i]<<' '<<post[1][i]<<'\n';

  	int Q = S.size();
  	std::vector<int> A(Q);
  	for (int i = 0; i < Q; ++i) {
    	A[i] = 0;
  	}

  	for(int t=0;t<SZ(S);++t){
  		int st=S[t];

  		for(int i=MAXL-1;i>=0;--i){
  			if(p[st][i][1] >= L[t]){
  				st=p[st][i][1];
  			}
  		}

  		int en=E[t];
  		for(int i=MAXL-1;i>=0;--i){
  			if(p[en][i][0] != -1 && p[en][i][0] <= R[t]){
  				en=p[en][i][0];
  			}
  		}
  		sweep[pre[1][st]].pb(mp(post[1][st], t), mp(pre[0][en], post[0][en]));
  	}
  	// In the seg tree pairs are (preB, preA)
  	root=new node(0,N-1);
  	for(int i=N-1;i>=0;--i){
  		int node = ipre[1][i];
  		root->up(pre[0][node], pre[1][node]);
  		for(auto x:sweep[i]){
  			int ind=x.f.s;
  			int m=root->rmin(x.s.f,x.s.s);
  			if(x.f.f >= m)A[ind]=1;
  			// cerr<<"Query "<<ind<<' '<<x.f.f<<' '<<m<<'\n';
  		}
  	}
  	
  	return A;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 33280 KB Output is correct
2 Correct 21 ms 33280 KB Output is correct
3 Correct 21 ms 33184 KB Output is correct
4 Correct 20 ms 33152 KB Output is correct
5 Correct 21 ms 33280 KB Output is correct
6 Correct 20 ms 33272 KB Output is correct
7 Correct 21 ms 33280 KB Output is correct
8 Correct 20 ms 33280 KB Output is correct
9 Correct 20 ms 33280 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 33280 KB Output is correct
2 Correct 21 ms 33280 KB Output is correct
3 Correct 21 ms 33184 KB Output is correct
4 Correct 20 ms 33152 KB Output is correct
5 Correct 21 ms 33280 KB Output is correct
6 Correct 20 ms 33272 KB Output is correct
7 Correct 21 ms 33280 KB Output is correct
8 Correct 20 ms 33280 KB Output is correct
9 Correct 20 ms 33280 KB Output is correct
10 Correct 28 ms 34168 KB Output is correct
11 Correct 28 ms 34168 KB Output is correct
12 Correct 27 ms 34176 KB Output is correct
13 Correct 32 ms 34432 KB Output is correct
14 Correct 27 ms 34304 KB Output is correct
15 Correct 29 ms 34296 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 880 ms 93032 KB Output is correct
2 Correct 952 ms 106728 KB Output is correct
3 Correct 828 ms 102504 KB Output is correct
4 Correct 741 ms 100768 KB Output is correct
5 Correct 752 ms 100968 KB Output is correct
6 Correct 827 ms 101272 KB Output is correct
7 Correct 741 ms 100200 KB Output is correct
8 Correct 915 ms 106856 KB Output is correct
9 Correct 750 ms 101992 KB Output is correct
10 Correct 543 ms 100456 KB Output is correct
11 Correct 569 ms 100328 KB Output is correct
12 Correct 652 ms 100072 KB Output is correct
13 Correct 1000 ms 113256 KB Output is correct
14 Correct 982 ms 113384 KB Output is correct
15 Correct 974 ms 113432 KB Output is correct
16 Correct 997 ms 113640 KB Output is correct
17 Correct 721 ms 100584 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 33280 KB Output is correct
2 Correct 21 ms 33280 KB Output is correct
3 Correct 21 ms 33184 KB Output is correct
4 Correct 20 ms 33152 KB Output is correct
5 Correct 21 ms 33280 KB Output is correct
6 Correct 20 ms 33272 KB Output is correct
7 Correct 21 ms 33280 KB Output is correct
8 Correct 20 ms 33280 KB Output is correct
9 Correct 20 ms 33280 KB Output is correct
10 Correct 28 ms 34168 KB Output is correct
11 Correct 28 ms 34168 KB Output is correct
12 Correct 27 ms 34176 KB Output is correct
13 Correct 32 ms 34432 KB Output is correct
14 Correct 27 ms 34304 KB Output is correct
15 Correct 29 ms 34296 KB Output is correct
16 Correct 880 ms 93032 KB Output is correct
17 Correct 952 ms 106728 KB Output is correct
18 Correct 828 ms 102504 KB Output is correct
19 Correct 741 ms 100768 KB Output is correct
20 Correct 752 ms 100968 KB Output is correct
21 Correct 827 ms 101272 KB Output is correct
22 Correct 741 ms 100200 KB Output is correct
23 Correct 915 ms 106856 KB Output is correct
24 Correct 750 ms 101992 KB Output is correct
25 Correct 543 ms 100456 KB Output is correct
26 Correct 569 ms 100328 KB Output is correct
27 Correct 652 ms 100072 KB Output is correct
28 Correct 1000 ms 113256 KB Output is correct
29 Correct 982 ms 113384 KB Output is correct
30 Correct 974 ms 113432 KB Output is correct
31 Correct 997 ms 113640 KB Output is correct
32 Correct 721 ms 100584 KB Output is correct
33 Correct 993 ms 102248 KB Output is correct
34 Correct 494 ms 66356 KB Output is correct
35 Correct 1128 ms 106456 KB Output is correct
36 Correct 933 ms 102504 KB Output is correct
37 Correct 1098 ms 105072 KB Output is correct
38 Correct 976 ms 103528 KB Output is correct
39 Correct 1008 ms 118360 KB Output is correct
40 Correct 1064 ms 112864 KB Output is correct
41 Correct 857 ms 103400 KB Output is correct
42 Correct 653 ms 101192 KB Output is correct
43 Correct 1157 ms 113168 KB Output is correct
44 Correct 966 ms 104960 KB Output is correct
45 Correct 873 ms 117480 KB Output is correct
46 Correct 849 ms 117480 KB Output is correct
47 Correct 954 ms 113512 KB Output is correct
48 Correct 974 ms 113512 KB Output is correct
49 Correct 985 ms 113512 KB Output is correct
50 Correct 975 ms 113512 KB Output is correct
51 Correct 992 ms 112188 KB Output is correct
52 Correct 971 ms 112096 KB Output is correct