제출 #603935

#제출 시각아이디문제언어결과실행 시간메모리
603935yuto1115늑대인간 (IOI18_werewolf)C++17
49 / 100
4057 ms43276 KiB
#include "werewolf.h" #include "bits/stdc++.h" #define rep(i, n) for(ll i = 0; i < ll(n); ++i) #define rep2(i, s, n) for(ll i = ll(s); i < ll(n); ++i) #define rrep(i, n) for(ll i = ll(n)-1; i >= 0; --i) #define pb push_back #define eb emplace_back #define all(a) a.begin(),a.end() #define SZ(a) int(a.size()) using namespace std; using ll = long long; using P = pair<int, int>; using vi = vector<int>; using vvi = vector<vi>; using vl = vector<ll>; using vvl = vector<vl>; using vb = vector<bool>; using vvb = vector<vb>; using vp = vector<P>; using vvp = vector<vp>; using vs = vector<string>; const int inf = 1001001001; const ll linf = 1001001001001001001; template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } else { return false; } } template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } else { return false; } } // {min, max} using S = P; const S e = {inf, -inf}; S op(S a, S b) { return {min(a.first, b.first), max(a.second, b.second)}; } class segtree { int n, log; vector<S> d; void update(int p) { assert(p < n); d[p] = op(d[2 * p], d[2 * p + 1]); } public: segtree(const vector<S> &init = {}) { log = 0; while (1 << log < SZ(init)) ++log; n = 1 << log; d.assign(2 * n, e); rep(i, SZ(init)) d[n + i] = init[i]; for (int i = n - 1; i >= 1; --i) update(i); } S prod(int l, int r) { assert(0 <= l and l <= r and r <= n); l += n, r += n; S res = e; while (l < r) { if (l & 1) res = op(res, d[l++]); if (r & 1) res = op(res, d[--r]); l >>= 1, r >>= 1; } return res; } }; vi check_validity(int n, vi x, vi y, vi s, vi e, vi l, vi r) { int m = SZ(x), q = SZ(s); vi ans(q); vvi G(n); rep(i, m) { G[x[i]].pb(y[i]); G[y[i]].pb(x[i]); } bool is_line = (m == n - 1); rep(i, n) is_line &= SZ(G[i]) <= 2; if (is_line) { vi ls; auto dfs = [&](auto &dfs, int u, int p) -> void { ls.pb(u); for (int v: G[u]) { if (v == p) continue; dfs(dfs, v, u); } }; rep(i, n) if (SZ(G[i]) == 1) { dfs(dfs, i, -1); break; } vi pos(n); rep(i, n) pos[ls[i]] = i; vp init(n); rep(i, n) init[i] = {ls[i], ls[i]}; segtree st(init); rep(i, q) { P ok_s, ok_e; { int ok = pos[s[i]], ng = -1; auto f = [&](int x) -> bool { return st.prod(x, pos[s[i]]).first >= l[i]; }; while (abs(ok - ng) > 1) { int mid = (ok + ng) / 2; if (f(mid)) ok = mid; else ng = mid; } ok_s.first = ok; } { int ok = pos[s[i]] + 1, ng = n + 1; auto f = [&](int x) -> bool { return st.prod(pos[s[i]], x).first >= l[i]; }; while (abs(ok - ng) > 1) { int mid = (ok + ng) / 2; if (f(mid)) ok = mid; else ng = mid; } ok_s.second = ok; } { int ok = pos[e[i]], ng = -1; auto f = [&](int x) -> bool { return st.prod(x, pos[e[i]]).second <= r[i]; }; while (abs(ok - ng) > 1) { int mid = (ok + ng) / 2; if (f(mid)) ok = mid; else ng = mid; } ok_e.first = ok; } { int ok = pos[e[i]] + 1, ng = n + 1; auto f = [&](int x) -> bool { return st.prod(pos[e[i]], x).second <= r[i]; }; while (abs(ok - ng) > 1) { int mid = (ok + ng) / 2; if (f(mid)) ok = mid; else ng = mid; } ok_e.second = ok; } if (ok_s.second > ok_e.first and ok_e.second > ok_s.first) ans[i] = 1; } } else { rep(i, q) { vb ok_s(n), ok_e(n); { auto dfs = [&](auto &dfs, int u) -> void { ok_s[u] = true; for (int v: G[u]) { if (v < l[i]) continue; if (ok_s[v]) continue; dfs(dfs, v); } }; dfs(dfs, s[i]); } { auto dfs = [&](auto &dfs, int u) -> void { ok_e[u] = true; for (int v: G[u]) { if (v > r[i]) continue; if (ok_e[v]) continue; dfs(dfs, v); } }; dfs(dfs, e[i]); } rep(j, n) if (ok_s[j] and ok_e[j]) ans[i] = 1; } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...