제출 #130605

#제출 시각아이디문제언어결과실행 시간메모리
130605sealnot123늑대인간 (IOI18_werewolf)C++14
0 / 100
836 ms114312 KiB
#include "werewolf.h" #include<bits/stdc++.h> #define x first #define y second #define pb push_back #define eb emplace_back #define all(a) (a).begin(),(a).end() #define SZ(a) (int)(a).size() using namespace std; typedef long long LL; typedef pair<LL,LL> PLL; typedef pair<int,int> PII; typedef double D; typedef long double LD; typedef vector<int> VI; const int N = 200005, Q = 400005; int n, q, m; struct A{ int q, u, t; bool operator <(const A& o) const{ return t<o.t; } }; vector<int> g[N], G[N], ans; vector<A> H, WW; int P[Q], sz[Q], ll[Q], rr[Q], p[N], dp[N], T; int st[N], en[N]; set<int> node[N]; set<int>::iterator IT; int fin(int i){ if(p[i]==i) return i; return fin(p[i]); } void merg(int a, int b, bool ww){ a = fin(a); b = fin(b); if(a == b) return ; if(dp[a]<dp[b]) swap(a,b); if(!ww) G[a].pb(b); else{ for(int it : node[b]) node[a].insert(it); } p[b] = a; dp[a] += dp[b]; } void dfs(int u){ st[u] = ++T; for(int e : G[u]) dfs(e); en[u] = T; } VI check_validity(int nn, VI X, VI Y, VI S, VI E, VI L, VI R) { q = SZ(S); n = nn; m = SZ(X); ans.resize(q); int i,j,k,l,a,b,c,d; for(i=0;i<m;i++){ g[X[i]].pb(Y[i]); g[Y[i]].pb(X[i]); } for(i=0;i<q;i++){ H.pb({i, S[i], L[i]}); WW.pb({i, E[i], R[i]}); } sort(all(H)); sort(all(WW)); // human preparation int nw; nw = q-1; for(i=0;i<n;i++) p[i]=i, dp[i]=1; for(i=n-1;i>=0;i--){ for(int e : g[i]){ if(e > i) merg(i,e,false); } while(nw>=0 && H[nw].t == -i){ a = fin(H[nw].u); b = H[nw].q; P[b] = a; sz[b] = dp[a]; nw--; } } for(i=0;i<n;i++){ if(p[i]==i) dfs(i); } for(i=0;i<q;i++){ ll[i] = st[P[i]]; rr[i] = st[P[i]]+sz[i]-1; } // werewolf prepareation nw=0; for(i=0;i<n;i++){ p[i] = i; dp[i] = 1; node[i].insert(st[i]); } for(i=0;i<n;i++){ for(int e : g[i]){ if(e < i) merg(i, e, true); } while(nw<q && WW[nw].t == i){ a = fin(WW[nw].u); b = WW[nw].q; IT = node[a].lower_bound(ll[b]); if(IT != node[a].end() && *IT <= rr[b]) ans[b] = 1; nw++; } } return ans; } /* 6 6 3 5 1 1 2 1 3 3 4 3 0 5 2 4 2 1 2 4 2 2 2 5 4 3 4 */

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

werewolf.cpp: In function 'VI check_validity(int, VI, VI, VI, VI, VI, VI)':
werewolf.cpp:61:9: warning: unused variable 'j' [-Wunused-variable]
   int i,j,k,l,a,b,c,d;
         ^
werewolf.cpp:61:11: warning: unused variable 'k' [-Wunused-variable]
   int i,j,k,l,a,b,c,d;
           ^
werewolf.cpp:61:13: warning: unused variable 'l' [-Wunused-variable]
   int i,j,k,l,a,b,c,d;
             ^
werewolf.cpp:61:19: warning: unused variable 'c' [-Wunused-variable]
   int i,j,k,l,a,b,c,d;
                   ^
werewolf.cpp:61:21: warning: unused variable 'd' [-Wunused-variable]
   int i,j,k,l,a,b,c,d;
                     ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...