Submission #541620

#TimeUsernameProblemLanguageResultExecution timeMemory
541620SlavicGWerewolf (IOI18_werewolf)C++17
15 / 100
4046 ms83620 KiB
#include "bits/stdc++.h" using namespace std; #define ll long long #define forn(i,n) for(int i=0;i<n;i++) #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(),v.rend() #define pb push_back #define sz(a) (int)a.size() template<typename T> struct LazySegmentTree{ int n; vector<T> t, lazy, a; T neutral, lazy_neutral; function<T(const T&, const T&)> merge; function<T(const T&, const T&)> upd; bool range_modif = false; LazySegmentTree(int _n, T _neutral, T _lazy_neutral, const function<T(const T&, const T&)> &_merge, const function<T(const T&, const T&)> &_upd, bool _range_modif){ range_modif = _range_modif; init(_n, _neutral, _lazy_neutral, _merge, _upd); } LazySegmentTree(vector<T> _a, T _neutral, T _lazy_neutral, const function<T(const T&, const T&)> &_merge, const function<T(const T&, const T&)> &_upd, bool _range_modif){ range_modif = _range_modif, a = _a; int _n = (int)a.size(); init(_n, _neutral, _lazy_neutral, _merge, _upd); build(1, 0, n - 1); } void init(int _n, T _neutral, T _lazy_neutral, const function<T(const T&, const T&)> &_merge, const function<T(const T&, const T&)> &_upd){ n = _n, neutral = _neutral, lazy_neutral = _lazy_neutral, merge = _merge, upd = _upd; t.assign(4 * n, neutral); lazy.assign(4 * n, lazy_neutral); } void build(int i, int l, int r){ if(l == r){ t[i] = a[l]; return; } int mid = (l + r) >> 1; build(2 * i, l, mid); build(2 * i + 1, mid + 1, r); t[i] = merge(t[2 * i], t[2 * i + 1]); } void push(int i, int l, int r){ if(lazy[i] == lazy_neutral)return; t[i] = upd(t[i], lazy[i] * (range_modif ? (r - l + 1) : 1)); if(l != r){ lazy[2 * i] = upd(lazy[2 * i], lazy[i]); lazy[2 * i + 1] = upd(lazy[2 * i + 1], lazy[i]); } lazy[i] = lazy_neutral; } void modif(int i, int l, int r, int tl, int tr, T val){ push(i, l, r); if(l > tr || r < tl)return; if(l >= tl && r <= tr){ lazy[i] = upd(lazy[i], val); push(i, l, r); return; } int mid = (l + r) >> 1; modif(2 * i, l, mid, tl, tr, val); modif(2 * i + 1, mid + 1, r, tl, tr, val); t[i] = merge(t[2 * i], t[2 * i + 1]); } T query(int i, int l, int r, int tl, int tr){ push(i, l, r); if(l > tr || r < tl)return neutral; if(l >= tl && r <= tr)return t[i]; int mid = (l + r) >> 1; T left = query(2 * i, l, mid, tl, tr); T right = query(2 * i + 1, mid + 1, r, tl, tr); return merge(left, right); } void modif(int l, int r, T val){ modif(1, 0, n - 1, l, r, val); } void modif(int poz, T val){ modif(1, 0, n - 1, poz, poz, val); } T query(int l, int r){ return query(1, 0, n - 1, l, r); } T query(int poz){ return query(1, 0, n - 1, poz, poz); } //n, neutral, lazy neutral, merge, upd, bool range update }; int mg(int a, int b) {return max(a, b);} int up(int a, int b) {return a+b;} const int N = 2e5 + 10; int d[N], s1[N], s2[N], in1[N], in2[N], f1 = 0, f2 = 0; vector<int> g1[N], g2[N]; int get(int a) { return d[a] = (d[a] == a ? a : get(d[a])); } void dfs1(int u) { s1[u] = 1; in1[u] = f1++; for(int v: g1[u]) { dfs1(v); s1[u] += s1[v]; } } void dfs2(int u) { s2[u] = 1; in2[u] = f2++; for(int v: g2[u]) { dfs2(v); s2[u] += s2[v]; } } struct query { int l, r, idx; }; const int S = 600; bool cmp(query a, query b) { pair<int, int> A = {a.l / S, a.r}; pair<int, int> B = {b.l / S, b.r}; return A < B; } vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r) { forn(i, N) d[i] = i; int m = sz(x), q = sz(l); vector<vector<int>> edges(n); vector<int> root1(q), root2(q); vector<int> ss[n + 5], ee[n + 5]; for(int i = 0;i < m; ++i) { edges[x[i]].pb(y[i]); edges[y[i]].pb(x[i]); } for(int i = 0;i < q; ++i) { ss[l[i]].pb(i); ee[r[i]].pb(i); } for(int i = n - 1; i >= 0; --i) { set<int> st; for(int v: edges[i]) { if(v < i) continue; st.insert(get(v)); } for(auto x: st) { g1[i].pb(x); d[x] = i; } for(auto x: ss[i]) root1[x] = get(s[x]); } forn(i, N) d[i] = i; for(int i = 0; i < n; ++i) { set<int> st; for(int v: edges[i]) { if(v > i) continue; st.insert(get(v)); } for(auto x: st) { g2[i].pb(x); d[x] = i; } for(auto x: ee[i]) { root2[x] = get(e[x]); } } dfs1(0); dfs2(n - 1); for(int i = 0; i < n; ++i) { assert(s1[i] > 0); } for(int i = n - 1; i >= 0; --i) { assert(s2[i] > 0); } vector<query> qr; for(int i = 0; i < q; ++i) { qr.pb({in2[root2[i]], in2[root2[i]] + s2[root2[i]] - 1, i}); } sort(all(qr), cmp); vector<pair<int, int>> v; for(int i = 0;i < n; ++i) { v.pb({in2[i], i}); } sort(all(v)); int L = 0, R = 0; LazySegmentTree<int> st(n, 0, 0, mg, up, 1); st.modif(in1[v[L].second], 1); vector<int> ans(q, 0); for(auto Q: qr) { while(R > Q.r) { st.modif(in1[v[R].second], -1); --R; } while(L < Q.l) { st.modif(in1[v[L].second], -1); ++L; } while(L > Q.l) { --L; st.modif(in1[v[L].second], 1); } while(R < Q.r) { ++R; st.modif(in1[v[R].second], 1); } int node = root1[Q.idx]; if(st.query(in1[node], in1[node] + s1[node] - 1) > 0) { ans[Q.idx] = 1; } } return ans; } /* void solve() { int n, m, q; cin >> n >> m >> q; vector<int> x(m), y(m), s(q), e(q), l(q), r(q); forn(i, m) cin >> x[i]; forn(i, m) cin >> y[i]; forn(i, q) cin >> s[i]; forn(i, q) cin >> e[i]; forn(i, q) cin >> l[i]; forn(i, q) cin >> r[i]; check_validity(n, x, y, s, e, l, r); } int32_t main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t = 1; //cin >> t; while(t--) { solve(); } } /* 6 6 3 5 1 1 3 3 5 1 2 3 4 0 2 4 4 5 2 2 4 1 2 3 2 2 4 */

Compilation message (stderr)

werewolf.cpp:279:1: warning: "/*" within comment [-Wcomment]
  279 | /*
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...