Submission #767315

#TimeUsernameProblemLanguageResultExecution timeMemory
767315amunduzbaevWerewolf (IOI18_werewolf)C++17
49 / 100
336 ms45176 KiB
#include "werewolf.h" #include "bits/stdc++.h" using namespace std; #ifndef EVAL #include "grader.cpp" #endif #define ar array typedef int64_t ll; typedef int32_t ii; //~ #define int ll struct ST{ vector<int> Min, Max; int N; ST(int N): N(N){ Min.resize(N << 2); Max.resize(N << 2); } void set(int i, int v, int lx, int rx, int x){ if(lx == rx) { Min[x] = Max[x] = v; return; } int m = (lx + rx) >> 1; if(i <= m) set(i, v, lx, m, x << 1); else set(i, v, m + 1, rx, x << 1 | 1); Min[x] = min(Min[x << 1], Min[x << 1 | 1]); Max[x] = max(Max[x << 1], Max[x << 1 | 1]); } void set(int i, int v){ set(i, v, 0, N, 1); } int first_less(int l, int r, int v, int lx, int rx, int x){ if(lx > r || rx < l) return -1; if(lx >= l && rx <= r){ if(Min[x] >= v) return -1; if(lx == rx) return lx; int m = (lx + rx) >> 1; if(Min[x << 1] < v) return first_less(l, r, v, lx, m, x << 1); else return first_less(l, r, v, m + 1, rx, x << 1 | 1); } int m = (lx + rx) >> 1; int res = first_less(l, r, v, lx, m, x << 1); if(res == -1) res = first_less(l, r, v, m + 1, rx, x << 1 | 1); return res; } int first_less(int l, int r, int v){ return first_less(l, r, v, 0, N, 1); } int last_less(int l, int r, int v, int lx, int rx, int x){ if(lx > r || rx < l) return -1; if(lx >= l && rx <= r){ if(Min[x] >= v) return -1; if(lx == rx) return lx; int m = (lx + rx) >> 1; if(Min[x << 1 | 1] < v) return last_less(l, r, v, m + 1, rx, x << 1 | 1); else return last_less(l, r, v, lx, m, x << 1); } int m = (lx + rx) >> 1; int res = last_less(l, r, v, m + 1, rx, x << 1 | 1); if(res == -1) res = last_less(l, r, v, lx, m, x << 1); return res; } int last_less(int l, int r, int v){ return last_less(l, r, v, 0, N, 1); } int get(int l, int r, int lx, int rx, int x){ if(lx > r || rx < l) return 0; if(lx >= l && rx <= r) return Max[x]; int m = (lx + rx) >> 1; return max(get(l, r, lx, m, x << 1), get(l, r, m + 1, rx, x << 1 | 1)); } int get(int l, int r){ return get(l, r, 0, N, 1); } int first_big(int l, int r, int v, int lx, int rx, int x){ if(lx > r || rx < l) return -1; if(lx >= l && rx <= r){ if(Max[x] <= v) return -1; if(lx == rx) return lx; int m = (lx + rx) >> 1; if(Max[x << 1] > v) return first_big(l, r, v, lx, m, x << 1); else return first_big(l, r, v, m + 1, rx, x << 1 | 1); } int m = (lx + rx) >> 1; int res = first_big(l, r, v, lx, m, x << 1); if(res == -1) res = first_big(l, r, v, m + 1, rx, x << 1 | 1); return res; } int first_big(int l, int r, int v){ return first_big(l, r, v, 0, N, 1); } int last_big(int l, int r, int v, int lx, int rx, int x){ if(lx > r || rx < l) return -1; if(lx >= l && rx <= r){ if(Max[x] <= v) return -1; if(lx == rx) return lx; int m = (lx + rx) >> 1; if(Max[x << 1 | 1] > v) return last_big(l, r, v, m + 1, rx, x << 1 | 1); else return last_big(l, r, v, lx, m, x << 1); } int m = (lx + rx) >> 1; int res = last_big(l, r, v, m + 1, rx, x << 1 | 1); if(res == -1) res = last_big(l, r, v, lx, m, x << 1); return res; } int last_big(int l, int r, int v){ return last_big(l, r, v, 0, N, 1); } }; 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(); vector<vector<int>> edges(n); for(int i=0;i<m;i++){ edges[x[i]].push_back(y[i]); edges[y[i]].push_back(x[i]); } if(n <= 3000 && m <= 6000 && q <= 3000){ vector<int> used_s(n), used_e(n); function<void(vector<int>&, int, int, int)> dfs = [&](vector<int>& used, int u, int l, int r){ used[u] = 1; for(auto x : edges[u]){ if(!used[x] && l <= x && x <= r){ dfs(used, x, l, r); } } }; vector<int> ans(q); for(int i=0;i<q;i++){ fill(used_s.begin(), used_s.end(), 0); fill(used_e.begin(), used_e.end(), 0); dfs(used_s, s[i], l[i], n); dfs(used_e, e[i], 0, r[i]); for(int j=0;j<n;j++){ if(used_s[j] && used_e[j]){ ans[i] = 1; break; } } } return ans; } ST tree(n); int root = -1; for(int i=0;i<n;i++){ if((int)edges[i].size() == 1){ root = i; break; } } assert(~root); vector<int> pos(n); int last = 0; function<void(int, int)> dfs = [&](int u, int p){ pos[u] = last++; for(auto x : edges[u]){ if(x == p) continue; dfs(x, u); } }; dfs(root, root); vector<int> a(n); for(int i=0;i<n;i++){ a[pos[i]] = i; tree.set(pos[i], i); } vector<int> ans(q); for(int j=0;j<q;j++){ int l_= pos[s[j]], r_ = pos[e[j]]; if(l_ < r_){ int L = tree.last_big(l_, r_, r[j]); int R = tree.first_less(l_, r_, l[j]); if(L == -1 || R == -1 || L + 1 < R){ ans[j] = 1; } //~ int p = tree.first_less(l_, r_, l[j]); //~ assert(p == -1 || l_ < p); //~ if(p == -1 || (l[j] <= a[p - 1] && a[p - 1] <= r[j] && tree.get(p, r_) <= r[j])){ //~ ans[j] = 1; //~ } } else { int R = tree.first_big(r_, l_, r[j]); int L = tree.last_less(r_, l_, l[j]); if(L == -1 || R == -1 || L + 1 < R){ ans[j] = 1; } //~ int p = tree.last_less(r_, l_, l[j]); //~ assert(p == -1 || p < l_); //~ if(p == -1 || (l[j] <= a[p + 1] && a[p + 1] <= r[j] && tree.get(r_, p) <= r[j])){ //~ ans[j] = 1; //~ } } } return ans; } /* 6 6 3 5 1 1 2 1 3 3 4 3 0 2 5 4 2 1 2 4 2 2 2 5 4 3 4 5 4 4 4 1 1 0 0 3 3 2 4 0 1 1 4 3 1 3 2 0 1 1 3 1 3 3 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...