제출 #138272

#제출 시각아이디문제언어결과실행 시간메모리
138272fredbr늑대인간 (IOI18_werewolf)C++17
0 / 100
4006 ms35904 KiB
#include "werewolf.h" #include <bits/stdc++.h> using namespace std; using vi = vector<int>; struct Seg { struct Node { int mini, maxi; static Node join(Node const& a, Node const& b) { return Node{min(a.mini, b.mini), max(a.maxi, b.maxi)}; } }; int n; vector<Node> tree; vector<int> const& v; Seg(vi const& v) : n(v.size()), tree(n*4), v(v) { build(0, 0, n-1); }; void build(int no, int l, int r) { if (l == r) { tree[no] = Node{v[l], v[l]}; return; } int m = (l+r)/2; build(no*2+1, l, m); build(no*2+2, m+1, r); tree[no] = Node::join(tree[no*2+1], tree[no*2+2]); } Node get(int no, int l, int r, int a, int b) { if (a <= l and r <= b) return tree[no]; int m = (l+r)/2; if (b <= m) return get(no*2+1, l, m, a, b); if (a > m) return get(no*2+2, m+1, r, a, b); return Node::join(get(no*2+1, l, m, a, b), get(no*2+2, m+1, r, a, b)); } }; int const maxn = 202020; vector<int> vt[maxn]; 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 q = S.size(); for (int i = 0; i < n; i++) { vt[X[i]].push_back(Y[i]); vt[Y[i]].push_back(X[i]); } int beg = 0; for (int i = 0; i < n; i++) if (vt[i].size() == 1) beg = i; vector<int> v(n); v[0] = beg; vector<int> pos(n, -1); pos[beg] = 0; for (int i = 1; i < n; i++) { int last = v[i-1]; for (int u : vt[last]) { if (pos[u] != -1) continue; v[i] = u; pos[u] = i; } } vector<int> res(q); Seg sg(v); for (int i = 0; i < q; i++) { int source = S[i], dest = E[i]; if (pos[source] > pos[dest]) swap(source, dest); int l = L[i], r = R[i]; int x = pos[source] - 1, y = pos[dest]; while (y-x > 1) { int m = (x+y+1)/2; if (sg.get(0, 0, n-1, m, pos[dest]).maxi <= r) y = m; else x = m; } // cout << i << " " << y << "\n"; res[i] = (sg.get(0, 0, n-1, pos[source], y).mini >= l and sg.get(0, 0, n-1, y, pos[dest]).maxi <= r); } return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...