제출 #406315

#제출 시각아이디문제언어결과실행 시간메모리
406315Antekb늑대인간 (IOI18_werewolf)C++14
34 / 100
438 ms42768 KiB
#include "werewolf.h" #include<bits/stdc++.h> #define st first #define nd second #define pb(x) push_back(x) #define mp(x, y) make_pair(x, y) using namespace std; typedef vector<int> vi; const int N=(1<<18); vi E[N]; int wsk; int vis[N], pre[N], tab[N+N], tab2[N+N]; void dfs(int v){ vis[v]=1; tab[N+wsk]=v; tab2[N+wsk]=v; pre[v]=wsk++; for(int u:E[v]){ if(!vis[u]){ dfs(u); } } } int lstmax(int l, int r, int c){ //cout<<"a "<<l<<" "<<r<<" "<<c<<"\n"; r++; int lew=-1; for(l+=N, r+=N; l<r; l>>=1, r>>=1){ if(l&1){ if(tab[l]>=c){ lew=l; } l++; } if(r&1){ if(tab[--r]>=c){ while(r<N){ if(tab[r+r+1]>=c)r=r+r+1; else r=r+r; } return r; } } } if(lew==-1)return -N-N; r=lew; while(r<N){ if(tab[r+r+1]>=c)r=r+r+1; else r=r+r; } return r; } int fstmax(int l, int r, int c){ //cout<<"b "<<l<<" "<<r<<" "<<c<<"\n"; r++; int lew=-1; for(l+=N, r+=N; l<r; l>>=1, r>>=1){ if(l&1){ if(tab[l]>=c){ while(l<N){ if(tab[l+l]>=c)l=l+l; else l=l+l+1; } return l; } l++; } if(r&1){ if(tab[--r]>=c){ lew=r; } } } if(lew==-1)return N+N; l=lew; while(l<N){ if(tab[l+l]>=c)l=l+l; else l=l+l+1; } return l; } int lstmin(int l, int r, int c){ //cout<<"c "<<l<<" "<<r<<" "<<c<<"\n"; r++; int lew=-1; for(l+=N, r+=N; l<r; l>>=1, r>>=1){ if(l&1){ if(tab2[l]<=c){ lew=l; } l++; } if(r&1){ if(tab2[--r]<=c){ while(r<N){ if(tab2[r+r+1]<=c)r=r+r+1; else r=r+r; } return r; } } } if(lew==-1)return -N-N; r=lew; while(r<N){ if(tab2[r+r+1]<=c)r=r+r+1; else r=r+r; } return r; } int fstmin(int l, int r, int c){ //cout<<"d "<<l<<" "<<r<<" "<<c<<"\n"; r++; int lew=-1; for(l+=N, r+=N; l<r; l>>=1, r>>=1){ if(l&1){ if(tab2[l]<=c){ while(l<N){ if(tab2[l+l]<=c)l=l+l; else l=l+l+1; } return l; } l++; } if(r&1){ if(tab2[--r]<=c){ lew=r; } } } if(lew==-1)return N+N; l=lew; while(l<N){ if(tab2[l+l]<=c)l=l+l; else l=l+l+1; } return l; } std::vector<int> check_validity(int n, vi X, vi Y, vi S, vi T, vi L, vi R) { int m=X.size(); for(int i=0; i<m; i++){ E[X[i]].pb(Y[i]); E[Y[i]].pb(X[i]); } for(int i=0; i<n; i++){ if(E[i].size()==1){ dfs(i); break; } } for(int i=N-1; i>0; i--){ tab[i]=max(tab[i+i], tab[i+i+1]); tab2[i]=min(tab2[i+i], tab2[i+i+1]); } int q = S.size(); std::vector<int> A(q); for (int i = 0; i < q; ++i){ if(pre[S[i]]<pre[T[i]]){ //cout<<"a"; int k=lstmax(pre[S[i]], pre[T[i]], R[i]+1), l=fstmin(pre[S[i]], pre[T[i]], L[i]-1); //cout<<k-N<<" "<<l-N<<"\n"; A[i]=(k<l-1); } else{ //cout<<"b"; int k=fstmax(pre[T[i]], pre[S[i]], R[i]+1), l=lstmin(pre[T[i]], pre[S[i]], L[i]-1); //cout<<k-N<<" "<<l-N<<"\n"; A[i]=(k>l+1); } } return A; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...