Submission #340685

#	Time	Username	Problem	Language	Result	Execution time	Memory
340685		keta_tsimakuridze	Werewolf (IOI18_werewolf)	C++14	100 / 100	2689 ms	204900 KiB

werewolf

#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];
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),
	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 (stderr)

werewolf.cpp: In function 'void dfs(int, int)':
werewolf.cpp:51:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  for(int i=0;i<V[t][u].size();i++){
      |              ~^~~~~~~~~~~~~~~
werewolf.cpp: In function 'void update(int, int, int, int, int)':
werewolf.cpp:67:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   67 |  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:124:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |     for(int j=0;j<v[i].size();j++){
      |                 ~^~~~~~~~~~~~
werewolf.cpp:135:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |     for(int j=0;j<v[i].size();j++){
      |                 ~^~~~~~~~~~~~
werewolf.cpp: At global scope:
werewolf.cpp:14:5: warning: 'int {anonymous}::read_int()' defined but not used [-Wunused-function]
   14 | int read_int() {
      |     ^~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51