oj.uz

답안 #340522

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
340522 2020-12-27T19:54:27 Z keta_tsimakuridze 늑대인간 (IOI18_werewolf) C++14
34 / 100
 2558 ms 234068 KB 
#include <cstdio>
#include <cstdlib>
#include <vector>
#include "werewolf.h"
#include<bits/stdc++.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,bbb;
vector<int>v[N],V[2][N],tree[4*N];
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);
	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()-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(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:110:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for(int j=0;j<v[i].size();j++){
      |                 ~^~~~~~~~~~~~
werewolf.cpp:121:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |     for(int j=0;j<v[i].size();j++){
      |                 ~^~~~~~~~~~~~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 103788 KB Output is correct
2 Correct 66 ms 103780 KB Output is correct
3 Correct 64 ms 103788 KB Output is correct
4 Correct 64 ms 103884 KB Output is correct
5 Correct 74 ms 103788 KB Output is correct
6 Correct 64 ms 103788 KB Output is correct
7 Correct 65 ms 103788 KB Output is correct
8 Correct 64 ms 103788 KB Output is correct
9 Incorrect 69 ms 103876 KB Output isn't correct

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 103788 KB Output is correct
2 Correct 66 ms 103780 KB Output is correct
3 Correct 64 ms 103788 KB Output is correct
4 Correct 64 ms 103884 KB Output is correct
5 Correct 74 ms 103788 KB Output is correct
6 Correct 64 ms 103788 KB Output is correct
7 Correct 65 ms 103788 KB Output is correct
8 Correct 64 ms 103788 KB Output is correct
9 Incorrect 69 ms 103876 KB Output isn't correct

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2558 ms 223028 KB Output is correct
2 Correct 1834 ms 231004 KB Output is correct
3 Correct 1845 ms 225620 KB Output is correct
4 Correct 1797 ms 223444 KB Output is correct
5 Correct 1877 ms 223188 KB Output is correct
6 Correct 2225 ms 223188 KB Output is correct
7 Correct 2496 ms 223176 KB Output is correct
8 Correct 1809 ms 230996 KB Output is correct
9 Correct 1405 ms 225832 KB Output is correct
10 Correct 1510 ms 223448 KB Output is correct
11 Correct 1621 ms 223316 KB Output is correct
12 Correct 1965 ms 222900 KB Output is correct
13 Correct 1589 ms 233796 KB Output is correct
14 Correct 1598 ms 234068 KB Output is correct
15 Correct 1508 ms 233944 KB Output is correct
16 Correct 1512 ms 233948 KB Output is correct
17 Correct 2519 ms 223024 KB Output is correct

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 103788 KB Output is correct
2 Correct 66 ms 103780 KB Output is correct
3 Correct 64 ms 103788 KB Output is correct
4 Correct 64 ms 103884 KB Output is correct
5 Correct 74 ms 103788 KB Output is correct
6 Correct 64 ms 103788 KB Output is correct
7 Correct 65 ms 103788 KB Output is correct
8 Correct 64 ms 103788 KB Output is correct
9 Incorrect 69 ms 103876 KB Output isn't correct