Submission #644725

#TimeUsernameProblemLanguageResultExecution timeMemory
644725khshgSynchronization (JOI13_synchronization)C++14
100 / 100
183 ms28556 KiB
#include <algorithm> #include <array> #include <bitset> #include <cassert> #include <chrono> #include <cmath> #include <complex> #include <cstring> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <numeric> #include <queue> #include <random> #include <set> #include <vector> using namespace std; /* ` ' ;,,, ` ' ,,,; `Y3S3333bo. : : .od3333Y3S' 3331O3D033b. : : .d333313D033 3L0V3Y' `Y3b. ` ' .d3Y' `YL0V33 jTH33! .db. Yb. ' ' .dY .db. 3TH33! `333 Y33Y `b ( ) d' Y33Y 333' 3MYb '" ,', "' dMY3 j3pr3C10USgf"' ':' `"?g3pr3C10USk 'Y' .3' d' 'b '3. 'Y' ! .3' db d'1 1`b db '3. ! d33 `' 3 ; ; 3 `' 33b d331b .g8 ',' 8g. d133b :333LOV333Y' 'Y33L0V3333: '! TH33333' `333TH33 !' '3Y `Y Y' Y3' Y Y ! ! */ using ll = long long; using db = long double; using str = string; // pairs using pi = pair<int, int>; using pl = pair<ll, ll>; using pd = pair<db, db>; #define mt make_tuple #define mp make_pair #define ff first #define ss second // vector template<class T> using V = vector<T>; using vi = V<int>; using vl = V<ll>; using vd = V<db>; using vb = V<bool>; using vpi = V<pi>; using vpl = V<pl>; #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define sz(a) (int)((a).size()) #define ini(a, b) memset(a, b, sizeof(a)) #define rsz resize #define pb push_back #define eb emplace_back #define ins insert #define arr array #define lb lower_bound #define ub upper_bound template<class T> int lwb(V<T>& a, const T& b) { return (int)(lb(all(a), b)-a.begin()); } template<class T> int upb(V<T>& a, const T& b) { return (int)(ub(all(a), b)-a.begin()); } // loops #define FOR(i, a, b) for (int i=a; i<(b); i++) #define F0R(i, a) for (int i=0; i<(a); i++) #define FORd(i, a, b) for (int i = (b)-1; i >= a; i--) #define F0Rd(i, a) for (int i = (a)-1; i >= 0; i--) #define trav(a, x) for (auto& a : x) template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; } template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; } template<class T> using pq = priority_queue<T>; template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>; ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up ceil() ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down floor() // consts const int MOD = (int)1e9+7; // 998244353; const int INF = (int)0x3f3f3f3f; // INF+INF < INF_MAX const ll INFL = ll(0x3f3f3f3f3f3f3f3f); // INFL+INFL < LLONG_MAX const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1}; // statement const int maxn=400000; int N, M, Q, info[maxn], Cinfo[maxn]; bool A[maxn]; pi edge[maxn]; vi adj[maxn]; //hld int par[4*maxn], ssz[maxn]; int Tm, pos[maxn], anc[maxn], flat[maxn]; void dfs_sz(int s, int p) { par[s]=p; ssz[s]=info[s]=1; if(sz(adj[s])>=2&&adj[s][0]==p) swap(adj[s][0], adj[s][1]); trav(u, adj[s]) if(u!=p) { dfs_sz(u, s); ssz[s]+=ssz[u]; if(ssz[adj[s][0]]<ssz[u]) swap(adj[s][0], u); } } void build_hld(int s) { pos[s]=Tm; flat[Tm]=s; ++Tm; trav(u, adj[s]) if(u!=par[s]) { if(u==adj[s][0]) anc[u]=anc[s]; else anc[u]=u; build_hld(u); } } //segment tree int st[4*maxn]; bool __[4*maxn]; #define tm ((tl+tr)/2) #define lv (2*v+1) #define rv (2*v+2) void build_st(int v, int tl, int tr) { if(tl==tr) st[v]=flat[tl]; else { build_st(lv, tl, tm); build_st(rv, tm+1, tr); st[v]=st[rv]; } } void update(int v, int tl, int tr, int ind) { if(tl==tr) { __[tl]^=1; st[v]=(__[tl]?-1:flat[tl]); } else { if(ind<=tm) update(lv, tl, tm, ind); else update(rv, tm+1, tr, ind); st[v]=st[(st[rv]==-1?lv:rv)]; } } int query(int v, int tl, int tr, int l, int r) { if(tl==l&&tr==r) return st[v]; if(r<=tm) return query(lv, tl, tm, l, r); if(l>tm) return query(rv, tm+1, tr, l, r); int o=query(rv, tm+1, tr, tm+1, r); if(o==-1) return query(lv, tl, tm, l, tm); return o; } int q(int s) { int res=-1; while(res==-1&&s!=-1) { if(pos[anc[s]]>pos[s]) exit(1); res=query(0, 0, N-1, pos[anc[s]], pos[s]); s=par[anc[s]]; } return (res==-1?0:res); } signed main() { cin.tie(nullptr)->sync_with_stdio(false); cin >> N >> M >> Q; F0R(i, N-1) { int U, V; cin >> U >> V; --U; --V; edge[i]=mp(U, V); adj[U].pb(V); adj[V].pb(U); } dfs_sz(0, -1); build_hld(0); build_st(0, 0, N-1); F0R(i, M) { int D, U, V; cin >> D; --D; tie(U, V)=edge[D]; if(par[U]==V) swap(U, V); if(!A[D]) info[q(U)]+=info[V]-Cinfo[V]; else info[V]=Cinfo[V]=info[q(U)]; update(0, 0, N-1, pos[V]); A[D]^=1; } F0R(i, Q) { int C; cin >> C; --C; cout << info[q(C)] << '\n'; } return 11^3^1<<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...
#Verdict Execution timeMemoryGrader output
Fetching results...