oj.uz

Submission #340503

# Submission time Handle Problem Language Result Execution time Memory
340503 2020-12-27T19:21:09 Z keta_tsimakuridze Werewolf (IOI18_werewolf) C++14
34 / 100
 2509 ms 240204 KB 
#include <cstdio>
#include <cstdlib>
#include <vector>
#include<bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int N=4e5+5;
int par[2][N],p[2][N][25],sz[2][N],tmin[2][N],tmout[2][N],timer,Lg,F;
vector<int>v[N],V[2][N],tree[4*N];
set<int> P[2][N];
namespace {

int read_int() {
  int x;
  if (scanf("%d", &x) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  return x;
}

}  
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);
	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;
		
		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()-1-ans+1; 
		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);
  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]++;
  	int x=Lca(S[i],L[i],0);
  	int y=Lca(E[i],R[i],1); //if(i==1)F=1;else F=0; cout<<x<<" "<<y<<"__"<<" "<<tmin[0][x]<<" "<<tmout[1][x]<<endl;
  	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:48:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for(int i=0;i<V[t][u].size();i++){
      |              ~^~~~~~~~~~~~~~~
werewolf.cpp: In function 'void update(int, int, int, int, int)':
werewolf.cpp:63:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   63 |  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: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++){
      |                 ~^~~~~~~~~~~~
werewolf.cpp:131:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |     for(int j=0;j<v[i].size();j++){
      |                 ~^~~~~~~~~~~~
werewolf.cpp: At global scope:
werewolf.cpp:13:5: warning: 'int {anonymous}::read_int()' defined but not used [-Wunused-function]
   13 | int read_int() {
      |     ^~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 103788 KB Output is correct
2 Correct 62 ms 103788 KB Output is correct
3 Correct 63 ms 103788 KB Output is correct
4 Correct 62 ms 103660 KB Output is correct
5 Correct 62 ms 103788 KB Output is correct
6 Correct 62 ms 103788 KB Output is correct
7 Correct 62 ms 103788 KB Output is correct
8 Correct 62 ms 103776 KB Output is correct
9 Incorrect 62 ms 103788 KB Output isn't correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 103788 KB Output is correct
2 Correct 62 ms 103788 KB Output is correct
3 Correct 63 ms 103788 KB Output is correct
4 Correct 62 ms 103660 KB Output is correct
5 Correct 62 ms 103788 KB Output is correct
6 Correct 62 ms 103788 KB Output is correct
7 Correct 62 ms 103788 KB Output is correct
8 Correct 62 ms 103776 KB Output is correct
9 Incorrect 62 ms 103788 KB Output isn't correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 2509 ms 230748 KB Output is correct
2 Correct 1859 ms 237652 KB Output is correct
3 Correct 1781 ms 232916 KB Output is correct
4 Correct 1754 ms 230868 KB Output is correct
5 Correct 1794 ms 230868 KB Output is correct
6 Correct 2171 ms 230736 KB Output is correct
7 Correct 2485 ms 230900 KB Output is correct
8 Correct 1831 ms 237440 KB Output is correct
9 Correct 1419 ms 232984 KB Output is correct
10 Correct 1522 ms 230868 KB Output is correct
11 Correct 1667 ms 231044 KB Output is correct
12 Correct 1976 ms 230584 KB Output is correct
13 Correct 1579 ms 239960 KB Output is correct
14 Correct 1555 ms 240092 KB Output is correct
15 Correct 1488 ms 240204 KB Output is correct
16 Correct 1507 ms 240084 KB Output is correct
17 Correct 2506 ms 230904 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 103788 KB Output is correct
2 Correct 62 ms 103788 KB Output is correct
3 Correct 63 ms 103788 KB Output is correct
4 Correct 62 ms 103660 KB Output is correct
5 Correct 62 ms 103788 KB Output is correct
6 Correct 62 ms 103788 KB Output is correct
7 Correct 62 ms 103788 KB Output is correct
8 Correct 62 ms 103776 KB Output is correct
9 Incorrect 62 ms 103788 KB Output isn't correct