제출 #76559

#제출 시각아이디문제언어결과실행 시간메모리
76559born2rule늑대인간 (IOI18_werewolf)C++14
0 / 100
1982 ms197708 KiB
#include <bits/stdc++.h> #include "werewolf.h" #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define ll long long #define db long double #define ii pair<int,int> #define vi vector<int> #define fi first #define se second #define sz(a) (int)(a).size() #define all(a) (a).begin(),(a).end() #define pb push_back #define mp make_pair #define FN(i, n) for (int i = 0; i < (int)(n); ++i) #define FEN(i,n) for (int i = 1;i <= (int)(n); ++i) #define rep(i,a,b) for(int i=a;i<b;i++) #define repv(i,a,b) for(int i=b-1;i>=a;i--) #define SET(A, val) memset(A, val, sizeof(A)) typedef tree<int ,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set ; // order_of_key (val): returns the no. of values less than val // find_by_order (k): returns the kth largest element.(0-based) #define TRACE #ifdef TRACE #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__) template <typename Arg1> void __f(const char* name, Arg1&& arg1){ cerr << name << " : " << arg1 << std::endl; } template <typename Arg1, typename... Args> void __f(const char* names, Arg1&& arg1, Args&&... args){ const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...); } #else #define trace(...) #endif const int N=200005; /*vi v[N]; bool vis[N]; void dfs(int u,int l,int r,vi &tmp,int type=0) { if(type==0 && u<l) return; if(type==1 && u>r) return; vis[u]=true; tmp.pb(u); for(int v1:v[u]) { if(vis[v1]) continue; dfs(v1,l,r,tmp,type); } } vi subtask12(int n,vi S,vi E,vi L,vi R) { int q=sz(S); vi ans(q,0); rep(i,0,q) { int x=S[i],y=E[i],l=L[i],r=R[i]; x++,y++,l++,r++; if(x<l || y>r) continue; vi tmp1,tmp2; rep(j,1,n+1) vis[j]=false; dfs(x,l,r,tmp1); rep(j,1,n+1) vis[j]=false; dfs(y,l,r,tmp2,1); sort(all(tmp1)); sort(all(tmp2)); bool ok=false; for(int x:tmp1) { int ind=lower_bound(all(tmp2),x)-tmp2.begin(); if(ind!=sz(tmp2) && tmp2[ind]==x) ok=true; } if(ok) ans[i]=1; } return ans; }*/ const int L=3*N,LN=20; vi ad[N]; int par[L],val[2][L],val2[L],p[2][LN][L]; vi v[2][L];//edges for 1st tree and 2nd tree int st[2][L],en[2][L],child[2][L],timer[]={1,1}; int rev[2][L],bit[L]; vector<ii> queries[L]; int finda(int u) { if(par[u]==u) return u; return par[u]=finda(par[u]); } int cnt; void dfs(int u,int type=0,int pa=0) { p[type][0][u]=pa; rev[type][timer[type]]=u; st[type][u]=timer[type]++; child[type][u]=1; for(int v1:v[type][u]) dfs(v1,type,pa),child[type][u]+=child[type][v1]; en[type][u]=timer[type]; } void update(int i,int val) { while(i<L) { bit[i]+=val; i+=(i&(-i)); } } int query(int i) { int ans=0; while(i) { ans+=bit[i]; i-=(i&(-i)); } return ans; } void calcdfs(int u,int type,bool keep,int n,vi &ans) { int mx=-1,bigchild=-1; for(int v1:v[type][u]) { if(child[type][v1]>mx) mx=child[type][v1],bigchild=v1; } for(int v1:v[type][u]) if(v1!=bigchild) calcdfs(v1,type,0,n,ans); if(bigchild!=-1) calcdfs(bigchild,type,keep,n,ans); for(int v1:v[type][u]) { if(v1==bigchild) continue; rep(i,st[type][v1],en[type][v1]) { int x=rev[type][i]; if(x>=1 && x<=n) update(st[1-type][x],1); } } if(u>=1 && u<=n) update(st[1-type][u],1); for(auto it:queries[u]) { int tmp=query(en[1-type][it.fi]-1)-query(st[1-type][it.fi]-1); if(tmp) ans[it.se]=1; } if(!keep) { rep(i,st[type][u],en[type][u]) { int x=rev[type][i]; if(x>=1 && x<=n) update(st[1-type][x],-1); } } } vi solve(int n,vi X,vi Y,vi S,vi E,vi L,vi R) { //let U be set of reachable nodes from s which are at >R, we need to represent it as a subtree, similarly for nodes<L cnt=n; rep(i,0,sz(X)) X[i]++,Y[i]++; rep(i,0,sz(X)) ad[min(X[i],Y[i])].pb(max(X[i],Y[i])); rep(i,1,n+1) par[i]=i,val[0][i]=n; repv(i,1,n)//add edges in reverse order { for(int v1:ad[i]) { int x=finda(i),y=finda(v1); if(x==y) continue; cnt++; par[x]=par[y]=par[cnt]=cnt;//make a new node v[0][cnt].pb(x); v[0][cnt].pb(y); val[0][cnt]=i;//index till which edges are added } } int root[2]; root[0]=cnt; rep(i,1,n+1) ad[i].clear(),par[i]=i,val[1][i]=1; rep(i,0,sz(X)) ad[max(X[i],Y[i])].pb(min(X[i],Y[i])); rep(i,2,n+1)//add edges in reverse order { for(int v1:ad[i]) { int x=finda(i),y=finda(v1); if(x==y) continue; cnt++; par[x]=par[y]=par[cnt]=cnt;//make a new node v[1][cnt].pb(x); v[1][cnt].pb(y); val[1][cnt]=i;//index till which edges are added } } root[1]=cnt; //make euler tour of both trees rep(i,0,2) dfs(root[i],i,root[i]); rep(k,0,2) rep(i,1,LN) rep(j,1,cnt+1) p[k][i][j]=p[k][i-1][p[k][i-1][j]]; vi ans(sz(S),0); rep(i,0,sz(S)) { int x=S[i],y=E[i],l=L[i],r=R[i]; x++,y++,l++,r++; if(x<l || y>r) continue; //find subtree corr. to x s.t. only nodes >=l are reachable int curr1=x; repv(i,0,LN) if(val[0][p[0][i][curr1]]>=l) curr1=p[0][i][curr1]; int curr2=y; repv(i,0,LN) if(val[1][p[1][i][curr2]]<=r) curr2=p[1][i][curr2]; //now check if subtrees of curr1 and curr2 intersect queries[curr1].pb(mp(curr2,i)); } calcdfs(root[0],0,0,n,ans); return ans; } vi check_validity(int n,vi X,vi Y,vi S,vi E,vi L,vi R) { int q=sz(S); /*rep(i,0,sz(X)) { X[i]++; Y[i]++; v[X[i]].pb(Y[i]); v[Y[i]].pb(X[i]); } if(n<=3000 && q<=3000) return subtask12(n,S,E,L,R);*/ return solve(n,X,Y,S,E,L,R); }

컴파일 시 표준 에러 (stderr) 메시지

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:226:7: warning: unused variable 'q' [-Wunused-variable]
   int q=sz(S);
       ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...