제출 #207954

#제출 시각아이디문제언어결과실행 시간메모리
207954red1108늑대인간 (IOI18_werewolf)C++17
0 / 100
1074 ms155456 KiB
#include "werewolf.h" #include <bits/stdc++.h> using namespace std; #define fi first #define se second typedef pair<int,int> pii; int n, m; //1 이 N->1, 2가 1->N순서 vector<int> tree1[200010], tree2[200010], gr[200010]; pii rn1[200010], rn2[200010]; int mi[20][200010], ma[20][200010], par1[20][200010], par2[20][200010]; int anc[200010], ord; int nh[200010], root[200010]; int findanc(int x){ if(x==anc[x]) return x; return anc[x]=findanc(anc[x]); } void dfs1(int x, int par){ //printf("dfs1(%d %d)\n", x, par); mi[0][x] = par; par1[0][x]=par; rn1[x].fi = ++ord; for(auto i:tree1[x]) if(i!=par){ dfs1(i,x); } rn1[x].se = ord; } void dfs2(int x, int par){ //printf("dfs2(%d %d)\n", x, par); ma[0][x] = par; par2[0][x]=par; rn2[x].fi = ++ord; nh[rn1[x].fi] = ord; for(auto i:tree2[x]) if(i!=par){ dfs2(i,x); } rn2[x].se = ord; } struct Node{ int sum, l, r; Node(){l=r=sum=0;} }; vector<Node> pst; void gang(int bef, int cur, int l, int r, int i){ pst[cur] = pst[bef]; pst[cur].sum++; if(l==r) return ; int m = (l+r)/2; if(i<=m){ pst[cur].l = pst.size(); pst.push_back(Node()); gang(pst[bef].l, pst[cur].l, l, m, i); } else{ pst[cur].r = pst.size(); pst.push_back(Node()); gang(pst[bef].r,pst[cur].r, m+1, r, i); } } int get(int bef, int cur, int l, int r, int s, int e){ if(r<s||e<l||s>e) return 0; if(s<=l&&r<=e) return pst[cur].sum - pst[bef].sum; return get(pst[bef].l, pst[cur].l, l, (l+r)/2, s, e) + get(pst[bef].r, pst[cur].r, (l+r)/2+1, r, s, e); } 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) { n = N; m = X.size(); for(int i=0;i<m;i++){ int a = X[i], b = Y[i]; a++;b++; gr[a].push_back(b); gr[b].push_back(a); } for(int i=1;i<=n;i++) anc[i]=i; for(int i=n;i>=1;i--){ for(auto j:gr[i]){ if(j<i) continue; int a = findanc(j), b = findanc(i); if(a==b) continue; anc[a]=b; tree1[a].push_back(b); tree1[b].push_back(a); } } for(int i=1;i<=n;i++) anc[i]=i; for(int i=1;i<=n;i++){ for(auto j:gr[i]){ if(j>i) continue; int a = findanc(j), b = findanc(i); if(a==b) continue; anc[a]=b; tree2[a].push_back(b); tree2[b].push_back(a); } } ord=0;dfs1(1, 0); ord=0;dfs2(n, 0); //cout<<"phase1"<<endl; pst.push_back(Node()); //for(int i=1;i<=n;i++) printf("nh[%d]=%d\n", i, nh[i]); for(int i=1;i<=n;i++){ root[i]=pst.size(); pst.push_back(Node()); gang(root[i-1], root[i], 1, n, nh[i]); } //cout<<"phase2"<<endl; for(int i=1;i<20;i++){ for(int j=1;j<=n;j++){ par1[i][j] = par1[i-1][par1[i-1][j]]; par2[i][j] = par2[i-1][par2[i-1][j]]; mi[i][j] = min(mi[i-1][j], mi[i-1][par1[i-1][j]]); ma[i][j] = max(ma[i-1][j], ma[i-1][par2[i-1][j]]); } } //for(int i=1;i<=n;i++) printf("i=%d (%d %d)\n", i, rn1[i].fi, rn2[i].fi); int Q = S.size(); std::vector<int> A(Q); for (int i = 0; i < Q; ++i) { S[i]++;E[i]++;L[i]++;R[i]++; int x = S[i], y = E[i]; for(int j=19;j>=0;j--){ if(mi[j][x]>=L[i]) x = par1[j][x]; if(ma[j][y]<=R[i]) y = par2[j][y]; } //printf("x = %d y = %d\n", x, y); int sum = get(root[rn1[x].fi-1], root[rn1[x].se], 1, n, rn2[y].fi, rn2[y].se); if(sum) A[i]=1; else A[i]=0; } 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...