제출 #299610

#제출 시각아이디문제언어결과실행 시간메모리
299610kshitij_sodani늑대인간 (IOI18_werewolf)C++14
100 / 100
1195 ms141540 KiB
#include <bits/stdc++.h> using namespace std; #define a first #define b second #define pb push_back typedef long long llo; #include "werewolf.h" vector<pair<int,int>> pre[200001]; vector<pair<int,int>> pre2[200001]; vector<pair<int,int>> pre3[200001]; vector<pair<int,int>> pre4[200001]; int par[200001]; int ss[200001]; vector<int> adj[200001]; vector<int> adj2[200001]; int find(int no){ if(par[no]==no){ return no; } par[no]=find(par[no]); return par[no]; } int co=-1; int st[200001]; int stt[200001]; void dfs(int no){ co++; st[no]=co; stt[co]=no; for(auto j:adj[no]){ dfs(j); } } int co2=-1; int st2[200001]; int stt2[200001]; void dfs2(int no){ co2++; st2[no]=co2; stt2[co2]=no; for(auto j:adj2[no]){ dfs2(j); } } pair<int,int> ran[200001]; pair<int,int> ran2[200001]; int vis[200001]; vector<int> tree[800001]; void add(int no,int l,int r,int aa,int bb,int i){ if(r<aa or l>bb){ return; } if(aa<=l and r<=bb){ tree[no].pb(i); } else{ int mid=(l+r)/2; add(no*2+1,l,mid,aa,bb,i); add(no*2+2,mid+1,r,aa,bb,i); } } int ans2[200001]; void update(int no,int l,int r,int i){ for(auto j:tree[no]){ if(vis[j]==0){ ans2[j]=1; } } tree[no].clear(); if(l<r){ int mid=(l+r)/2; if(i<=mid){ update(no*2+1,l,mid,i); } else{ update(no*2+2,mid+1,r,i); } } } //vector<int> pre5[200001]; vector<pair<pair<int,int>,int>> pre5[200001]; vector<int> pre6[200001]; vector<int> check_validity(int n,vector<int> xx,vector<int> yy, vector<int> ss3,vector<int> ee, vector<int> l,vector<int> r) { int m=xx.size(); for(int i=0;i<m;i++){ pre[min(xx[i],yy[i])].pb({xx[i],yy[i]}); pre2[max(xx[i],yy[i])].pb({xx[i],yy[i]}); } for(int i=0;i<n;i++){ par[i]=i; ss[i]=1; } int q=ss3.size(); for(int i=0;i<q;i++){ pre3[l[i]].pb({ss3[i],i}); pre4[r[i]].pb({ee[i],i}); } vector<pair<pair<int,int>,int>> qq; for(int i=n-1;i>=0;i--){ for(auto j:pre[i]){ int x=find(j.a); int y=find(j.b); if(x!=y){ // cout<<x<<":"<<y<<endl; adj[x].pb(y); par[y]=x; ss[x]+=ss[y]; } } for(auto j:pre3[i]){ qq.pb({{find(j.a),ss[find(j.a)]},j.b}); // cout<<j.a<<"."<<find(j.a)<<"/"<<ss[find(j.a)]<<"/"<<j.b<<endl; } } dfs(find(0)); for(auto j:qq){ ran[j.b]={st[j.a.a],st[j.a.a]+j.a.b-1}; } /*for(int i=0;i<q;i++){ cout<<ran[i].a<<":"<<ran[i].b<<endl; for(int j=ran[i].a;j<=ran[i].b;j++){ cout<<stt[j]<<","; } cout<<endl; }*/ for(int i=0;i<n;i++){ par[i]=i; ss[i]=1; } vector<pair<pair<int,int>,int>> qq2; for(int i=0;i<n;i++){ for(auto j:pre2[i]){ int x=find(j.a); int y=find(j.b); if(x!=y){ adj2[x].pb(y); //cout<<x<<":"<<y<<endl; par[y]=x; ss[x]+=ss[y]; } } for(auto j:pre4[i]){ qq2.pb({{find(j.a),ss[find(j.a)]},j.b}); } } dfs2(find(0)); for(auto j:qq2){ ran2[j.b]={st2[j.a.a],st2[j.a.a]+j.a.b-1}; } vector<int> ans; for(int i=0;i<q;i++){ pre5[ran[i].a].pb({ran2[i],i}); pre6[ran[i].b].pb(i); /*for(int j=ran[i].a;j<=ran[i].b;j++){ vis[stt[j]]+=1; } int kk=0; for(int j=ran2[i].a;j<=ran2[i].b;j++){ vis[stt2[j]]+=1; if(vis[stt2[j]]==2){ kk=-1; } } ans.pb(kk); for(int j=ran[i].a;j<=ran[i].b;j++){ vis[stt[j]]-=1; } for(int j=ran2[i].a;j<=ran2[i].b;j++){ vis[stt2[j]]-=1; }*/ } for(int i=0;i<n;i++){ for(auto j:pre5[i]){ add(0,0,n-1,j.a.a,j.a.b,j.b); } update(0,0,n-1,st2[stt[i]]); for(auto j:pre6[i]){ vis[j]=1; } } for(int i=0;i<q;i++){ ans.pb(ans2[i]); } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...