제출 #969668

#제출 시각아이디문제언어결과실행 시간메모리
969668tnknguyen_늑대인간 (IOI18_werewolf)C++14
0 / 100
116 ms127404 KiB
#include <bits/stdc++.h> using namespace std; #define endl '\n' #define vi vector<int> #define pii pair<int, int> const int MX = 1e6 + 5; vector<int> gr[4][MX]; int vis[MX]; int n, m, q; vi X, Y, S, E, L, R; struct KRT{ int n; vector<int> p; KRT(int N){ this->n = N; p.assign(N + 5, 0); for(int i=1; i<=n; ++i){ p[i] = i; } } int get(int u){ return (u == p[u] ? u : p[u] = get(p[u])); } void add(int u, int v, int k){ u = get(u), v = get(v); if(u == v){ return; } p[v] = u; gr[k][u].push_back(v); } }; struct BIT{ int n; vector<int> f; BIT(int N){ this->n = N + 5; f.assign(N + 5, 0); } void update(int i, int val){ while(i < n){ f[i] += val; i += (i & -i); } } int get(int i){ int ans = 0; while(i > 0){ ans += f[i]; i -= (i & -i); } return ans; } int get(int l, int r){ return get(r) - get(l - 1); } }; struct query{ int l, r, e, s, idx; }; int in[4][MX], ou[4][MX]; int eu[4][MX]; int id = 0; void dfs(int u, int p, int k){ eu[k][++id] = u; in[k][u] = id; for(int v : gr[k][u]){ if(v != p){ dfs(v, u, k); eu[k][++id] = u; ou[k][u] = id; } } } vector<int> check_validity(int n, vi X, vi Y, vi S, vi E, vi L, vi R){ //returns boolean vector. for(int i=0; i<m; ++i){ int u = X[i], v = Y[i]; gr[1][u].push_back(v); gr[1][v].push_back(u); } KRT up(n), dn(n); for(int i=1; i<=n; ++i){ for(int u : gr[1][i]){ if(vis[u] == 1){ up.add(i, u, 2); } } vis[i] = 1; } for(int i=n; i>=1; --i){ for(int u : gr[1][i]){ if(vis[u] == 2){ dn.add(i, u, 3); } } vis[i] = 2; } for(int i=1; i<=n; ++i){ if(up.get(i) == i){ dfs(i, 0, 2); break; } } id = 0; for(int i=1; i<=n; ++i){ if(dn.get(i) == i){ dfs(i, 0, 3); break; } } vector<query> Q; vector<int> ans; for(int i=0; i<q; ++i){ int s = S[i], e = E[i], l = L[i], r = R[i]; set<int> se; for(int j=in[3][l]+1; j<ou[3][l]; ++j){ se.insert(eu[3][j]); } int f = 0; for(int j=in[2][r]+1; j<ou[2][r]; ++j){ if(se.find(eu[2][j]) != se.end()){ f = 1; } } if(se.find(s) == se.end() || se.find(e) == se.end()){ f = 0; } ans.push_back(f); } return ans; } // int32_t main() { // ios_base::sync_with_stdio(0); // cin.tie(0); // cout.tie(0); // freopen("main.inp","r",stdin); // freopen("main.out","w",stdout); // cin>>n>>m>>q; // for(int i=1; i<=m; ++i){ // int u, v; // cin>>u>>v; // ++u, ++v; // X.push_back(u); // Y.push_back(v); // } // for(int i=1; i<=q; ++i){ // int s, e, l, r; // cin>>s>>e>>l>>r; // ++s, ++e, ++l, ++r; // S.push_back(s), E.push_back(e), L.push_back(l), R.push_back(r); // } // vector<int> ans = check_validity(n, X, Y, S, E, L, R); // for(int x : ans){ // cout<<x<<' '; // } // return 0; // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...