제출 #1198240

#제출 시각아이디문제언어결과실행 시간메모리
1198240dubabuba늑대인간 (IOI18_werewolf)C++20
15 / 100
3512 ms34608 KiB
#include "werewolf.h" #include <bits/stdc++.h> using namespace std; #define ff first #define ss second #define MP make_pair const int mxn = 3030; int n, m, q; int Hans[mxn], Wans[mxn]; typedef pair<int, int> pii; typedef vector<int> vi; typedef bitset<mxn> bi; bi hun[mxn], dog[mxn]; struct Tree { int anc[mxn * 2], cnt; vector<int> chi[mxn * 2]; vector<int> query[mxn * 2]; Tree() { memset(anc, -1, sizeof anc); } int ancestor(int u) { return anc[u] < 0 ? u : anc[u] = ancestor(anc[u]); } int unite(int u, int v) { u = ancestor(u); v = ancestor(v); if(u == v) return -1; anc[cnt] += anc[u]; anc[cnt] += anc[v]; anc[u] = cnt; anc[v] = cnt; chi[cnt].push_back(u); chi[cnt].push_back(v); return cnt++; } bi dfs(int u, bool flag) { if(u < n) { bi ret = 0; ret[u] = 1; if(flag) { for(int i : query[u]) hun[i] = ret; } else { for(int i : query[u]) dog[i] = ret; } return ret; } bi ret = 0; for(int v : chi[u]) ret |= dfs(v, flag); if(flag) { for(int i : query[u]) hun[i] = ret; } else { for(int i : query[u]) dog[i] = ret; } return ret; } }; Tree humans, wolves; vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) { n = N; m = X.size(); q = S.size(); vector<pii> HQ[n]; vector<pii> WQ[n]; for(int i = 0; i < m; i++) { int mn = min(X[i], Y[i]); int mx = max(X[i], Y[i]); HQ[mn].push_back(MP(-1, mx)); WQ[mx].push_back(MP(-1, mn)); } for(int i = 0; i < q; i++) { int l = L[i], r = R[i]; HQ[l].push_back(MP(i, S[i])); WQ[r].push_back(MP(i, E[i])); } // cout << "\nWolves\n"; wolves.cnt = n; for(int u = 0; u < n; u++) { for(pii p : WQ[u]) { int i = p.ff; int v = p.ss; if(i == -1) { int a = wolves.unite(u, v); // cout << u << ' ' << v << " -> " << a << endl; } else { Wans[i] = wolves.ancestor(v); wolves.query[Wans[i]].push_back(i); // cout << "query " << i << ": " << u << ' ' << v << " = " << Wans[i] << endl; } } } // cout << "\nHumans\n"; humans.cnt = n; for(int u = n - 1; u >= 0; u--) { for(pii p : HQ[u]) { int i = p.ff; int v = p.ss; if(i == -1) { int a = humans.unite(u, v); // cout << u << ' ' << v << " -> " << a << endl; } else { Hans[i] = humans.ancestor(v); humans.query[Hans[i]].push_back(i); // cout << "query " << i << ": " << u << ' ' << n - 1 << " = " << Hans[i] << endl; } } } bool vis[n * 2]; memset(vis, 0, sizeof vis); for(int i = 0; i < n; i++) { int a = wolves.ancestor(i); if(!vis[a]) { wolves.dfs(a, 1); } } memset(vis, 0, sizeof vis); for(int i = 0; i < n; i++) { int a = humans.ancestor(i); if(!vis[a]) { humans.dfs(a, 0); } } vi ret; bi buba = 0; for(int i = 0; i < q; i++) { buba = hun[i] & dog[i]; // cout << S[i] << " -> " << L[i] << ' ' << R[i] << ": "; // for(int k = 0; k < n; k++) // cout << hun[i][k]; // cout << endl; // cout << E[i] << " -> " << L[i] << ' ' << R[i] << ": "; // for(int k = 0; k < n; k++) // cout << dog[i][k]; // cout << endl; if(buba.count()) ret.push_back(1); else ret.push_back(0); // cout << endl; } return ret; } /* 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 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...