oj.uz

Submission #340687

# Submission time Handle Problem Language Result Execution time Memory
340687 2020-12-28T07:49:53 Z keta_tsimakuridze Werewolf (IOI18_werewolf) C++14
100 / 100
 2704 ms 196312 KB 
#include "werewolf.h"
#include <cstdio>
#include <cstdlib>
#include <vector>
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int par[2][N],p[2][N][25],sz[2][N],tmin[2][N],tmout[2][N],timer,Lg,F,bbb,i;
vector<int>v[N],V[2][N],tree[4*N];
vector<pair<int,int> >e[2];
set<int> P[2][N];
int find_parent(int u,int t){
	if(par[t][u]==u) return u;
	return par[t][u]=find_parent(par[t][u],t);
}
void merge(int u,int v,int t){
	int p1=find_parent(u,t);
	int p2=find_parent(v,t);
	if(p1==p2) return;  
	if(!t)V[t][u].push_back(*P[t][p2].begin()),V[t][*P[t][p2].begin()].push_back(u);
	else V[t][u].push_back(*--P[t][p2].end()),V[t][*--P[t][p2].end()].push_back(u),
	e[1].push_back({u,*--P[t][p2].end()}),e[1].push_back({*--P[t][p2].end(),u});
	if(P[t][p1].size()<P[t][p2].size()) swap(p1,p2);
	while(P[t][p2].size()){
		int cc=*P[t][p2].begin();
		P[t][p1].insert(cc);
		par[t][cc]=p1;
		P[t][p2].erase(cc);
	}
}
void dfs(int u,int t){
	timer++;
	tmin[t][u]=timer;  
	for(int j=1;j<Lg;j++){
		p[t][u][j]=p[t][p[t][u][j-1]][j-1];
	}
	for(int i=0;i<V[t][u].size();i++){
		if(p[t][u][0]==V[t][u][i]) continue;
		if(!t && V[t][u][i]<u) cout<<1/bbb<<endl;
		if(t && V[t][u][i]>u) cout<<1/bbb<<endl;
		p[t][V[t][u][i]][0]=u;
		dfs(V[t][u][i],t);
	}
	tmout[t][u]=timer;
}
void update(int u,int ind,int l,int r,int val){
	if(l>ind || r<ind) return;
	if(l==r) {
		tree[u].push_back(val);
		return;
	}
	tree[u].push_back(val);
	if(tree[u].size()==r-l+1) sort(tree[u].begin(),tree[u].end());
	int mid=(l+r)/2;
	update(2*u,ind,l,mid,val);
	update(2*u+1,ind,mid+1,r,val);
}
int getans(int u,int start,int end,int l,int r,int L,int R){
	if(l>end || r<start) return 0; 
	if(l>=start && r<=end){
		int ans=-1; 
		int le=0;int ri=tree[u].size()-1; 
		while(le<=ri){
			int mid=(le+ri)/2; 
			if(tree[u][mid]<L){
				ans=mid; le=mid+1;
			}
			else ri=mid-1;
		} 
		int cnt=ans+1; 
		 ans=tree[u].size();
		 le=0; ri=tree[u].size()-1;
		while(le<=ri){
			int mid=(le+ri)/2;
			if(tree[u][mid]>R){
				ans=mid; ri=mid-1;
			}
			else le=mid+1;
		}
		cnt+=tree[u].size()-ans; 
		return cnt;
	}
	int mid=(l+r)/2;
	return getans(2*u,start,end,l,mid,L,R)+getans(2*u+1,start,end,mid+1,r,L,R);
}
int Lca(int u,int m,int t){
	for(int i=Lg;i>=0;i--){
		if(p[t][u][i] && ((!t && p[t][u][i]>=m)||(t && p[t][u][i]<=m))){
			u=p[t][u][i];
		}
	}
	return u;
}
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) {
  int M = X.size();
  Lg=log2(N)+1;
  for(int i=1;i<=N;i++)
  for(int j=0;j<=1;j++)
  par[j][i]=i,P[j][i].insert(i);
  for(int i=0;i<M;i++){
  	X[i]++; Y[i]++;
  	v[X[i]].push_back(Y[i]);
  	v[Y[i]].push_back(X[i]);
  } 
  for(int i=N;i>=1;i--){
  	sort(v[i].begin(),v[i].end());
  		for(int j=0;j<v[i].size();j++){
  			int nxt=v[i][j];
  			if(nxt>i){
  				merge(i,nxt,0);
			  }
		  }
  } 
  timer=0;
  dfs(1,0);
   for(int i=1;i<=N;i++){
  	reverse(v[i].begin(),v[i].end());
  		for(int j=0;j<v[i].size();j++){
  			int nxt=v[i][j];
  			if(nxt<i){
  				merge(i,nxt,1);
			  }
		  }
  }
  int Q=S.size();vector<int>Ans(Q);
  timer=0;
  dfs(N,1);
  for(int i=1;i<=N;i++){
  	update(1,tmin[0][i],1,N,tmin[1][i]);
  } 
 
  for(int  i=0;i<Q;i++){
  	S[i]++;
  	E[i]++;
  	L[i]++;
  	R[i]++; F=i;
  	int x=Lca(S[i],L[i],0);
  	int y=Lca(E[i],R[i],1); 
  	if(tmout[0][x]-tmin[0][x]+1-getans(1,tmin[0][x],tmout[0][x],1,N,tmin[1][y],tmout[1][y])) Ans[i]=1;
  	else Ans[i]=0; 
  }
  return Ans; 
}

Compilation message

werewolf.cpp: In function 'void dfs(int, int)':
werewolf.cpp:37:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for(int i=0;i<V[t][u].size();i++){
      |              ~^~~~~~~~~~~~~~~
werewolf.cpp: In function 'void update(int, int, int, int, int)':
werewolf.cpp:53:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |  if(tree[u].size()==r-l+1) sort(tree[u].begin(),tree[u].end());
      |     ~~~~~~~~~~~~~~^~~~~~~
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:109:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     for(int j=0;j<v[i].size();j++){
      |                 ~^~~~~~~~~~~~
werewolf.cpp:120:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for(int j=0;j<v[i].size();j++){
      |                 ~^~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 52076 KB Output is correct
2 Correct 32 ms 52076 KB Output is correct
3 Correct 34 ms 52076 KB Output is correct
4 Correct 32 ms 52076 KB Output is correct
5 Correct 33 ms 52076 KB Output is correct
6 Correct 32 ms 52076 KB Output is correct
7 Correct 32 ms 52092 KB Output is correct
8 Correct 33 ms 52076 KB Output is correct
9 Correct 32 ms 52076 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 52076 KB Output is correct
2 Correct 32 ms 52076 KB Output is correct
3 Correct 34 ms 52076 KB Output is correct
4 Correct 32 ms 52076 KB Output is correct
5 Correct 33 ms 52076 KB Output is correct
6 Correct 32 ms 52076 KB Output is correct
7 Correct 32 ms 52092 KB Output is correct
8 Correct 33 ms 52076 KB Output is correct
9 Correct 32 ms 52076 KB Output is correct
10 Correct 47 ms 53924 KB Output is correct
11 Correct 46 ms 53996 KB Output is correct
12 Correct 46 ms 53740 KB Output is correct
13 Correct 43 ms 54124 KB Output is correct
14 Correct 44 ms 54252 KB Output is correct
15 Correct 52 ms 53996 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 2622 ms 173860 KB Output is correct
2 Correct 1862 ms 181692 KB Output is correct
3 Correct 1797 ms 176596 KB Output is correct
4 Correct 1820 ms 174236 KB Output is correct
5 Correct 1866 ms 173908 KB Output is correct
6 Correct 2248 ms 173780 KB Output is correct
7 Correct 2522 ms 174292 KB Output is correct
8 Correct 1807 ms 181716 KB Output is correct
9 Correct 1393 ms 176432 KB Output is correct
10 Correct 1520 ms 174164 KB Output is correct
11 Correct 1712 ms 173908 KB Output is correct
12 Correct 2024 ms 173932 KB Output is correct
13 Correct 1614 ms 184788 KB Output is correct
14 Correct 1591 ms 184788 KB Output is correct
15 Correct 1520 ms 184788 KB Output is correct
16 Correct 1495 ms 184856 KB Output is correct
17 Correct 2498 ms 174092 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 52076 KB Output is correct
2 Correct 32 ms 52076 KB Output is correct
3 Correct 34 ms 52076 KB Output is correct
4 Correct 32 ms 52076 KB Output is correct
5 Correct 33 ms 52076 KB Output is correct
6 Correct 32 ms 52076 KB Output is correct
7 Correct 32 ms 52092 KB Output is correct
8 Correct 33 ms 52076 KB Output is correct
9 Correct 32 ms 52076 KB Output is correct
10 Correct 47 ms 53924 KB Output is correct
11 Correct 46 ms 53996 KB Output is correct
12 Correct 46 ms 53740 KB Output is correct
13 Correct 43 ms 54124 KB Output is correct
14 Correct 44 ms 54252 KB Output is correct
15 Correct 52 ms 53996 KB Output is correct
16 Correct 2622 ms 173860 KB Output is correct
17 Correct 1862 ms 181692 KB Output is correct
18 Correct 1797 ms 176596 KB Output is correct
19 Correct 1820 ms 174236 KB Output is correct
20 Correct 1866 ms 173908 KB Output is correct
21 Correct 2248 ms 173780 KB Output is correct
22 Correct 2522 ms 174292 KB Output is correct
23 Correct 1807 ms 181716 KB Output is correct
24 Correct 1393 ms 176432 KB Output is correct
25 Correct 1520 ms 174164 KB Output is correct
26 Correct 1712 ms 173908 KB Output is correct
27 Correct 2024 ms 173932 KB Output is correct
28 Correct 1614 ms 184788 KB Output is correct
29 Correct 1591 ms 184788 KB Output is correct
30 Correct 1520 ms 184788 KB Output is correct
31 Correct 1495 ms 184856 KB Output is correct
32 Correct 2498 ms 174092 KB Output is correct
33 Correct 2564 ms 176224 KB Output is correct
34 Correct 429 ms 72300 KB Output is correct
35 Correct 2622 ms 180820 KB Output is correct
36 Correct 2544 ms 174904 KB Output is correct
37 Correct 2605 ms 179672 KB Output is correct
38 Correct 2596 ms 176088 KB Output is correct
39 Correct 1912 ms 196308 KB Output is correct
40 Correct 2021 ms 182716 KB Output is correct
41 Correct 2437 ms 178644 KB Output is correct
42 Correct 2339 ms 175188 KB Output is correct
43 Correct 2704 ms 185464 KB Output is correct
44 Correct 2618 ms 179416 KB Output is correct
45 Correct 2061 ms 196312 KB Output is correct
46 Correct 2472 ms 196260 KB Output is correct
47 Correct 1619 ms 184660 KB Output is correct
48 Correct 1605 ms 184948 KB Output is correct
49 Correct 1507 ms 184916 KB Output is correct
50 Correct 1539 ms 184904 KB Output is correct
51 Correct 2080 ms 183308 KB Output is correct
52 Correct 2012 ms 183456 KB Output is correct