Submission #964661

#TimeUsernameProblemLanguageResultExecution timeMemory
964661fve5Werewolf (IOI18_werewolf)C++17
49 / 100
400 ms41528 KiB
#include <bits/stdc++.h> #include "werewolf.h" using namespace std; class SegTree { vector<int> arr; int sz, s; int upper_bound_right(int l, int r, int d, int n, int nb, int ne) { if (nb >= r || ne <= l || arr[n] <= d) return sz; if (nb + 1 == ne) return nb; int lq = upper_bound_right(l, r, d, 2 * n, nb, (nb + ne) / 2); if (lq != sz) return lq; return upper_bound_right(l, r, d, 2 * n + 1, (nb + ne) / 2, ne); } int upper_bound_left(int l, int r, int d, int n, int nb, int ne) { if (nb >= r || ne <= l || arr[n] <= d) return -1; if (nb + 1 == ne) return nb; int rq = upper_bound_left(l, r, d, 2 * n + 1, (nb + ne) / 2, ne); if (rq != -1) return rq; return upper_bound_left(l, r, d, 2 * n, nb, (nb + ne) / 2); } public: int upper_bound_left(int l, int r, int d) { return upper_bound_left(l, r, d, 1, 0, s); } int upper_bound_right(int l, int r, int d) { return upper_bound_right(l, r, d, 1, 0, s); } SegTree(int N, const vector<int> &a) : sz(N) { s = 1 << (int)ceil(log2(N)); arr.resize(2 * s); for (int i = 0; i < N; i++) arr[i + s] = a[i]; for (int i = s - 1; i > 0; i--) arr[i] = max(arr[2 * i], arr[2 * i + 1]); } }; vector<int> solve_naive( int N, int M, int Q, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R ) { vector<vector<int>> adj(N); for (int i = 0; i < M; i++) { adj[X[i]].push_back(Y[i]); adj[Y[i]].push_back(X[i]); } vector<int> ans(Q); for (int i = 0; i < Q; i++) { vector<array<bool, 2>> visited(N); queue<pair<int, bool>> q; q.emplace(S[i], 0); while (!q.empty()) { auto [node, st] = q.front(); q.pop(); if (visited[node][st]) continue; visited[node][st] = true; for (auto x: adj[node]) { if (!st && x >= L[i]) q.emplace(x, st); if (st && x <= R[i]) q.emplace(x, st); } if (!st && L[i] <= node && node <= R[i]) q.emplace(node, 1); } ans[i] = visited[E[i]][1]; } return ans; } vector<int> solve_line( int N, int M, int Q, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R ) { vector<vector<int>> adj(N); for (int i = 0; i < M; i++) { adj[X[i]].push_back(Y[i]); adj[Y[i]].push_back(X[i]); } int curr = find_if(adj.begin(), adj.end(), [](const vector<int> &arr) { return arr.size() == 1; }) - adj.begin(); vector<int> line; line.push_back(curr); int old = -1; for (int i = 0; i < N - 1; i++) { curr = adj[curr][adj[curr][0] == old]; old = line.back(); line.push_back(curr); } vector<int> mline(N); transform(line.begin(), line.end(), mline.begin(), [](int x) { return -x; }); vector<int> pos_of(N); for (int i = 0; i < N; i++) pos_of[line[i]] = i; SegTree segtree(N, line), msegtree(N, mline); vector<int> ans(Q); for (int i = 0; i < Q; i++) { int l1 = msegtree.upper_bound_left(0, pos_of[S[i]] + 1, -L[i]); int r1 = msegtree.upper_bound_right(pos_of[S[i]], N, -L[i]); int l2 = segtree.upper_bound_left(0, pos_of[E[i]] + 1, R[i]); int r2 = segtree.upper_bound_right(pos_of[E[i]], N, R[i]); ans[i] = !((l2 >= r1 - 1) || (r2 <= l1 + 1)); } return ans; } 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(); int Q = S.size(); if (N <= 3000 && M <= 6000 && Q <= 3000) { return solve_naive(N, M, Q, X, Y, S, E, L, R); } return solve_line(N, M, Q, X, Y, S, E, L, 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...