Submission #599704

#TimeUsernameProblemLanguageResultExecution timeMemory
599704skittles1412Werewolf (IOI18_werewolf)C++17
49 / 100
616 ms86492 KiB
#include "bits/extc++.h" using namespace std; template <typename T> void dbgh(const T& t) { cerr << t << endl; } template <typename T, typename... U> void dbgh(const T& t, const U&... u) { cerr << t << " | "; dbgh(u...); } #ifdef DEBUG #define dbg(...) \ cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \ dbgh(__VA_ARGS__); #else #define dbg(...) #define cerr \ if (false) \ cerr #endif using vi = vector<int>; #define endl "\n" #define long int64_t #define sz(x) int((x).size()) template <bool mn> struct ST { static int op(int x, int y) { if (mn) { return min(x, y); } else { return max(x, y); } } int n; vector<vector<int>> v; ST(const vector<int>& arr) : n(sz(arr)), v(__lg(n) + 2, vector<int>(n)) { v[0] = arr; for (int i = 1; (1 << i) <= n; i++) { for (int j = 0; j + (1 << i) <= n; j++) { v[i][j] = op(v[i - 1][j], v[i - 1][j + (1 << (i - 1))]); } } } int query(int l, int r) { int k = __lg(r - l + 1); return op(v[k][l], v[k][r - (1 << k) + 1]); } }; template <typename T> T reversed(T t) { reverse(begin(t), end(t)); return t; } struct Solver { int n; vector<int> arr, iarr; ST<true> mn; ST<false> mx; Solver(const vector<int>& arr): n(sz(arr)), arr(arr), iarr(n), mn(arr), mx(arr) { for (int i = 0; i < n; i++) { iarr[arr[i]] = i; } } int solve(int src, int dest, int ql, int qr) { src = iarr[src]; dest = iarr[dest]; if (src > dest) { return -1; } int x1, x2; { int l = src, r = dest; while (l < r) { int mid = (l + r + 1) / 2; if (mn.query(src, mid) >= ql) { l = mid; } else { r = mid - 1; } } x1 = l; } { int l = src, r = dest; while (l < r) { int mid = (l + r) / 2; if (mx.query(mid, dest) <= qr) { r = mid; } else { l = mid + 1; } } x2 = r; } return x1 >= x2; } }; vi check_validity(int n, vi us, vi vs, vi qsrc, vi qdest, vi ql, vi qr) { int m = sz(us), q = sz(qsrc); vector<int> graph[n]; for (int i = 0; i < m; i++) { graph[us[i]].push_back(vs[i]); graph[vs[i]].push_back(us[i]); } if (n <= 3000 && m <= 6000 && q <= 3000) { vector<int> ans(q); for (int qi = 0; qi < q; qi++) { int src = qsrc[qi], dest = qdest[qi], l = ql[qi], r = qr[qi]; bool vis[n][2] {}; vector<pair<int, int>> q; auto push = [&](int u, int t) -> void { if (!vis[u][t]) { vis[u][t] = true; q.emplace_back(u, t); } }; push(src, 0); while (sz(q)) { auto [u, t] = q.back(); q.pop_back(); if (l <= u && u <= r && !t) { push(u, 1); } for (auto& v : graph[u]) { if ((!t && v >= l) || (t && v <= r)) { push(v, t); } } } ans[qi] = vis[dest][1]; } return ans; } vector<int> arr; for (int i = 0; i < n; i++) { if (sz(graph[i]) == 1) { int prv = 0; while (sz(arr) < n) { arr.push_back(i); for (auto& a : graph[i]) { prv ^= a; } swap(prv, i); } break; } } Solver s1(arr), s2(reversed(arr)); vector<int> ans(q); for (int qi = 0; qi < q; qi++) { int src = qsrc[qi], dest = qdest[qi], l = ql[qi], r = qr[qi]; int cans = s1.solve(src, dest, l, r); if (cans == -1) { cans = s2.solve(src, dest, l, r); } ans[qi] = cans; } 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...