제출 #413631

#제출 시각아이디문제언어결과실행 시간메모리
413631_fractal늑대인간 (IOI18_werewolf)C++14
100 / 100
1257 ms106064 KiB
#include "werewolf.h" #include <iostream> using namespace std; #define pb push_back #define F first #define S second const int N = 200200; int n; vector<int> g[N]; vector<pair<pair<int, int>, pair<int, int>>> p[N]; struct tree { int t[N << 2]; void upd(int pos, int val, int v = 1, int tl = 1, int tr = n) { if (tl == tr) return t[v] = val, void(); int tm = tl + tr >> 1; if (pos <= tm) upd(pos, val, v * 2, tl, tm); else upd(pos, val, v * 2 + 1, tm + 1, tr); t[v] = max(t[v * 2], t[v * 2 + 1]); } int get(int l, int r, int v = 1, int tl = 1, int tr = n) { if (l <= tl && tr <= r) return t[v]; if (r < tl || tr < l) return 0; int tm = tl + tr >> 1; return max(get(l, r, v * 2, tl, tm), get(l, r, v * 2 + 1, tm + 1, tr)); } } t; struct tree_dsu { int p[N], sz[N], root, up[20][N], LG = 18; int tin[N], tout[N], tick, pos[N]; vector<int> h[N]; int mxup(int v, int k) { if (v == k) return v; for (int i = LG; i >= 0; --i) { int u = up[i][v]; if (u >= 0 && u >= k) v = u; } return v; } int mnup(int v, int k) { if (v == k) return v; for (int i = LG; i >= 0; --i) { int u = up[i][v]; if (u >= 0 && u <= k) v = u; } return v; } void dfs(int v, int p = -1) { tin[v] = ++tick; pos[tick] = v; up[0][v] = p; for (int i = 1; i <= LG; ++i) { if (up[i - 1][v] == -1) up[i][v] = -1; else up[i][v] = up[i - 1][up[i - 1][v]]; } for (auto to : h[v]) dfs(to, v); tout[v] = tick; } void init(int n) { for (int i = 0; i < n; ++i) p[i] = i, sz[i] = 1, h[i].clear(); } int get(int v) { return p[v] = (v == p[v] ? v : get(p[v])); } void unite(int v, int u) { if ((v = get(v)) == (u = get(u))) return; h[v].pb(u); root = v; sz[v] += sz[u]; p[u] = v; } } ds, sd; vector<int> check_validity(int _n, vector<int> U, vector<int> V, vector<int> S, vector<int> E, vector<int> L, vector<int> R) { int q = S.size(); int m = U.size(); n = _n; int r; vector<int> ans(q, 0); ds.init(n); sd.init(n); for (int i = 0; i < m; ++i) { g[U[i]].pb(V[i]); g[V[i]].pb(U[i]); } for (int i = n - 1; i >= 0; --i) { for (auto to : g[i]) { if (to > i) ds.unite(i, to); } } for (int i = 0; i < n; ++i) { for (auto to : g[i]) { if (to < i) sd.unite(i, to); } } ds.dfs(ds.root); sd.dfs(sd.root); for (int i = 0, l1, r1, l2, r2, v, u; i < q; ++i) { v = ds.mxup(S[i], L[i]); u = sd.mnup(E[i], R[i]); l1 = ds.tin[v], r1 = ds.tout[v]; l2 = sd.tin[u], r2 = sd.tout[u]; p[r1].pb({{i, l1}, {l2, r2}}); } for (int i = 1; i <= n; ++i) { t.upd(sd.tin[ds.pos[i]], i); for (auto it : p[i]) { if (t.get(it.S.F, it.S.S) >= it.F.S) ans[it.F.F] = 1; else ans[it.F.F] = 0; } } return ans; }

컴파일 시 표준 에러 (stderr) 메시지

werewolf.cpp: In member function 'void tree::upd(int, int, int, int, int)':
werewolf.cpp:21:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
werewolf.cpp: In member function 'int tree::get(int, int, int, int, int)':
werewolf.cpp:34:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
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:102:6: warning: unused variable 'r' [-Wunused-variable]
  102 |  int r;
      |      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...