Submission #1083973

#TimeUsernameProblemLanguageResultExecution timeMemory
1083973underwaterkillerwhaleSynchronization (JOI13_synchronization)C++17
0 / 100
745 ms262144 KiB
#include <bits/stdc++.h> #define ll long long #define pii pair<int,int> #define pll pair<ll,ll> #define rep(i,m,n) for(int i=(m); i<=(n); i++) #define reb(i,m,n) for(int i=(m); i>=(n); i--) #define iter(id, v) for(auto id : v) #define fs first #define se second #define MP make_pair #define pb push_back #define bit(msk, i) ((msk >> i) & 1) #define SZ(v) (ll)v.size() #define ALL(v) v.begin(),v.end() using namespace std; mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count()); ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); } const int N = 2e5 + 7; const int Mod = 1e9 + 7; const ll INF = 1e18; const ll BASE = 137; const int szBL = 350; int n, Q, K; pii ed[N]; vector<int> ke[N]; int pid[N]; int pa[N], nC[N], high[N], par[N][25]; int Head[N], ein[N]; bool stt[N]; struct Node2 { Node2 *lc, *rc; int val; Node2 () { lc = rc = NULL; val = 0; } Node2 (int _val) { lc = rc = NULL; val = _val; } Node2 (Node2 *lcc, Node2 *rcc) { lc = lcc; rc = rcc; val = max(lcc->val, rcc->val); } }; struct Node { Node *lc, *rc; int val; Node () { lc = rc = NULL; val = 0; } Node (int _val) { lc = rc = NULL; val = _val; } Node (Node *lcc, Node *rcc) { lc = lcc; rc = rcc; val = lcc->val & rcc->val; } }; Node *croot[N]; Node2 *croot2[N]; struct Persistent_Segment_Tree { Node *root[N]; int m; Node *build (int l, int r) { if (l == r) return new Node(); int mid = l + r >> 1; return new Node(build (l, mid), build (mid + 1, r)); } void init (int n) { m = n; root[0] = croot[0] = build(1, m); } Node *update (Node *curr, int l, int r, int pos) { if (l == r) { Node *cur = new Node(0); cur->val = curr->val ^ 1; return cur; } int mid = l + r >> 1; if (mid < pos) return new Node(curr->lc, update (curr->rc, mid + 1, r, pos)); else return new Node(update (curr->lc, l, mid, pos), curr->rc); } int get (Node *curr, int l, int r, int u, int v) { if (l > v || r < u) return 1; if (l >= u && r <= v) return curr->val; int mid = l + r >> 1; return get (curr->lc, l, mid, u, v) & get (curr->rc, mid + 1, r, u, v); } Node *update (int pos) { static int n_root = 0; ++n_root; return root[n_root] = update (root[n_root - 1], 1, m, pos); } int get (Node* rt, int u, int v ) { return get (rt, 1, m, u, v); } }ST; struct Persistent_Segment_Tree2 { Node2 *root[N * 2]; int m; Node2 *build (int l, int r) { if (l == r) return new Node2(1); int mid = l + r >> 1; return new Node2(build (l, mid), build (mid + 1, r)); } void init (int n) { m = n; root[0] = croot2[0] = build(1, m); } Node2 *update (Node2 *curr, int l, int r, int pos, int val, bool typ) { if (l == r) { Node2 *cur = new Node2(0); if (typ == 1) { cur->val = val; } else { cur->val = curr->val + val; } return cur; } int mid = l + r >> 1; if (mid < pos) return new Node2(curr->lc, update (curr->rc, mid + 1, r, pos, val, typ)); else return new Node2(update (curr->lc, l, mid, pos, val, typ), curr->rc); } int get (Node2 *curr, int l, int r, int pos) { if (l > pos || r < pos) return 0; if (l == r) return curr->val; int mid = l + r >> 1; return max(get (curr->lc, l, mid, pos), get (curr->rc, mid + 1, r, pos)); } Node2 *update (int pos, int val, bool typ) { static int n_root = 0; ++n_root; return root[n_root] = update (root[n_root - 1], 1, m, pos, val, typ); } int get (Node2 *rt, int pos) { return get (rt, 1, m, pos); } }ST2; void pdfs (int u, int p) { high[u] = high[p] + 1; pa[u] = p; par[u][0] = p; rep (i, 1, 20) par[u][i] = par[par[u][i - 1]][i - 1]; nC[u] = 1; iter (&v, ke[u]) { if (v != p) { pdfs(v, u); nC[u] += nC[v]; } } } void hld (int u, int p) { static int time_dfs = 0; Head[u] = p; ein[u] = ++time_dfs; int mxV = -1; iter (&v, ke[u]) if (v != pa[u] && (mxV == -1 || nC[v] > nC[mxV])) mxV = v; if (mxV != -1) hld(mxV, p); iter (&v, ke[u]) { if (v == pa[u] || v == mxV) continue; hld(v, v); } } int label (int state, int u) { while (u != 0) { bool cnc = ST.get(croot[state], ein[Head[u]], ein[u]); if (cnc == 0) { if (ST.get(croot[state], ein[u], ein[u]) == 0) return u; reb (i, 20, 0) { int cur = par[u][i]; if (high[cur] >= high[Head[u]] && ST.get(croot[state], ein[cur], ein[u])) { u = cur; } } return pa[u]; } u = pa[Head[u]]; } assert(0); } int getVal (int state, int u) { return ST2.get(croot2[state], ein[label(state, u)]); } void Connect (int state, int p) { int u = ed[p].fs, v = ed[p].se; int prvid = pid[p]; if (high[u] > high[v]) swap(u, v); int delta = getVal(state - 1, v); if (pid[p] != -1) { delta -= getVal(pid[p], v); } // cout << u <<" "<<v<<" "<<getVal(state - 1,u)<<" "<<getVal(state - 1, v)<< " " <<delta<<"\n"; croot2[state] = ST2.update (ein[label(state - 1, u)], delta, 0); croot[state] = ST.update (ein[v]); } void Detach (int state, int p) { int u = ed[p].fs, v = ed[p].se; if (high[u] > high[v]) swap(u, v); int delta = getVal(state - 1, u); croot2[state] = ST2.update (ein[u], delta, 1); croot2[state] = ST2.update (ein[v], delta, 1); croot[state] = ST.update (ein[v]); pid[p] = state; } void solution () { cin >> n >> Q >> K; rep (i, 1, n - 1) { int u, v; cin >> u >> v; ed[i] = MP(u, v); ke[u].pb(v); ke[v].pb(u); } pdfs(1, 0); hld(1, 1); ST.init(n); ST2.init(n); rep (i, 1, n) pid[i] = -1; rep (i, 1, Q) { int p; cin >> p; stt[p] ^= 1; if (stt[p] == 1) { Connect(i, p); } else { Detach(i, p); } // cout << i<<","<<stt[p]<<": "<<ed[p].fs <<" "<<ed[p].se<<" "<<label(6) <<" dda"<< val[3]<<" "<<getVal(label(6))<<"\n"; // if (i == 11) { // rep (u, 1, n) cout << ST.get(ein[u], ein[u]) <<" "; // cout<<"hih\n"; // } } rep (i, 1, K) { int X; cin >> X; cout << getVal(Q, X) <<"\n"; } } #define file(name) freopen(name".inp","r",stdin); \ freopen(name".out","w",stdout); int main () { // file("c"); ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0); int num_Test = 1; // cin >> num_Test; while (num_Test--) solution(); } /* no bug challenge +4 mình có muốn dùng mảng này không? 10 20 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 9 4 6 3 5 3 6 9 3 7 2 4 8 2 5 1 6 5 1 6 6 */

Compilation message (stderr)

synchronization.cpp: In member function 'Node* Persistent_Segment_Tree::build(int, int)':
synchronization.cpp:85:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |         int mid = l + r >> 1;
      |                   ~~^~~
synchronization.cpp: In member function 'Node* Persistent_Segment_Tree::update(Node*, int, int, int)':
synchronization.cpp:100:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |         int mid = l + r >> 1;
      |                   ~~^~~
synchronization.cpp: In member function 'int Persistent_Segment_Tree::get(Node*, int, int, int, int)':
synchronization.cpp:110:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  110 |         int mid = l + r >> 1;
      |                   ~~^~~
synchronization.cpp: In member function 'Node2* Persistent_Segment_Tree2::build(int, int)':
synchronization.cpp:131:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  131 |         int mid = l + r >> 1;
      |                   ~~^~~
synchronization.cpp: In member function 'Node2* Persistent_Segment_Tree2::update(Node2*, int, int, int, int, bool)':
synchronization.cpp:151:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  151 |         int mid = l + r >> 1;
      |                   ~~^~~
synchronization.cpp: In member function 'int Persistent_Segment_Tree2::get(Node2*, int, int, int)':
synchronization.cpp:161:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  161 |         int mid = l + r >> 1;
      |                   ~~^~~
synchronization.cpp: In function 'void Connect(int, int)':
synchronization.cpp:227:9: warning: unused variable 'prvid' [-Wunused-variable]
  227 |     int prvid = pid[p];
      |         ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...