제출 #878069

#제출 시각아이디문제언어결과실행 시간메모리
878069sleepntsheep늑대인간 (IOI18_werewolf)C++17
100 / 100
857 ms159528 KiB
#define SHINLENA2 #ifndef SHINLENA #include "werewolf.h" #endif #include <iostream> #include <algorithm> #include <numeric> #include <vector> #include <cstddef> #include <cassert> using namespace std; #define NN 200000 struct kruskal_reconstruction_tree { vector<int> p, tin, tout, rv; int l; vector<vector<int>> g; kruskal_reconstruction_tree(int n, int n0) : p(n), tin(n), tout(n), rv(n), l(n0), g(n) { iota(p.begin(), p.end(), 0); } int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); } int unite(int x, int y) { x = find(x); y = find(y); if (x == y) return 0; g[p[x] = p[y] = ++l] = {x, y}; return 1; } int timer = 0; void dfs(int u, int p) { rv[tin[u] = timer++] = u; for (auto v : g[u]) if (v != p) dfs(v, u); tout[u] = timer - 1; } void tour() { for (int i = l +1; i--;) if (!tin[i]) dfs(i, i); } }; vector<int> t[NN<<3]; void add(int v, int l, int r, int p, int k) { t[v].push_back(k); if (l == r) return; if (p <= (l+r)/2) add(2*v+1, l, (l+r)/2, p, k); else add(2*v+2, (l+r)/2+1, r, p, k); } int qry(int v, int l, int r, int x, int y, int k) { if (r < x || y < l) return 1e9; if (x <= l && r <= y) { auto it = lower_bound(t[v].begin(), t[v].end(), k); return it == t[v].end() ? 1e9 : *it; } return min(qry(2*v+1, l, (l+r)/2, x, y, k), qry(2*v+2, (l+r)/2+1, r, x, y, k)); } vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) { int M = X.size(); kruskal_reconstruction_tree krt1(N+M, N-1); kruskal_reconstruction_tree krt2(N+M, N-1); int Q = S.size(); vector<int> A(Q); vector<vector<int>> g(N); for (int i = 0; i < M; ++i) g[X[i]].push_back(Y[i]), g[Y[i]].push_back(X[i]); /* build krt */ vector<int> rtl(Q), rtr(Q); { vector<vector<int>> byl(N), byr(N); for (int i = 0; i < Q; ++i) byl[L[i]].push_back(i), byr[R[i]].push_back(i); for (int i = N; i--;) { for (auto v : g[i]) if (v >= i) krt1.unite(v, i); for (auto j : byl[i]) rtl[j] = krt1.find(S[j]); } for (int i = 0; i < N; ++i) { for (auto v : g[i]) if (v <= i) krt2.unite(v, i); for (auto j : byr[i]) rtr[j] = krt2.find(E[j]); } } krt1.tour(); krt2.tour(); int LL = krt1.timer - 1; /* build merge sort tree */ { vector<pair<int, int>> ins; for (int i = 0; i < N; ++i) ins.emplace_back(krt2.tin[i], krt1.tin[i]); sort(ins.begin(), ins.end()); for (auto [x, y] : ins) add(0, 0, LL, y, x); } for (int i = 0; i < Q; ++i) { A[i] = qry(0, 0, LL, krt1.tin[rtl[i]], krt1.tout[rtl[i]], krt2.tin[rtr[i]]) <= krt2.tout[rtr[i]]; } return A; } #ifdef SHINLENA int main() { int n,m,q; cin>>n>>m>>q; vector<int>x,y,s,e,l,r; for (int u,v,i=0;i<m;++i)cin>>u>>v, x.push_back(u), y.push_back(v); for (int a,b,c,d,i=0;i<q;++i) { cin>>a>>b>>c>>d; s.push_back(a); e.push_back(b); l.push_back(c); r.push_back(d); } auto A = check_validity(n,x,y,s,e,l,r); for (auto x : A) cout << x << endl; return 0; } #endif /* 6 6 3 5 1 1 3 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 '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:116:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  116 |         for (int i = 0; i < N; ++i)
      |         ^~~
werewolf.cpp:118:14: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  118 |              sort(ins.begin(), ins.end());
      |              ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...