Submission #1277736

#TimeUsernameProblemLanguageResultExecution timeMemory
1277736PlayVoltzSynchronization (JOI13_synchronization)C++20
100 / 100
279 ms36244 KiB
#include <cstdio> #include <stdio.h> #include <stdbool.h> #include <iostream> #include <map> #include <vector> #include <climits> #include <stack> #include <string> #include <queue> #include <algorithm> #include <set> #include <unordered_set> #include <unordered_map> #include <cmath> #include <cctype> #include <bitset> #include <iomanip> #include <cstring> #include <numeric> #include <cassert> #include <random> using namespace std; #define int long long #define pii pair<int, int> #define mp make_pair #define pb push_back #define fi first #define se second int n, counter=1; vector<int> ft, in, out, val, pp; vector<vector<int> > twok, graph; void dfs(int node, int p){ in[node]=counter++; twok[node][0]=p; for (int i=1; i<20; ++i)twok[node][i]=twok[twok[node][i-1]][i-1]; for (auto num:graph[node])if (num!=p)dfs(num, node); out[node]=counter; } void up(int i, int v){ for(;i<ft.size();i+=i&-i)ft[i]+=v; } int query(int i){ int res=0; for (;i;i-=i&-i)res+=ft[i]; return res; } int par(int a){ for (int i=19; i>=0; --i)if (query(in[a])==query(in[twok[a][i]]))a=twok[a][i]; return a; } int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int m, q, a, b, e; cin>>n>>m>>q; twok.resize(n+1, vector<int>(20)); in.resize(n+1); out.resize(n+1); graph.resize(n+1); val.resize(n+1, 1); pp.resize(n+1, 0); ft.resize(n+2, 0); vector<pii> edges(n); vector<bool> t(n, 0); for (int i=1; i<n; ++i){ cin>>edges[i].fi>>edges[i].se; graph[edges[i].fi].pb(edges[i].se); graph[edges[i].se].pb(edges[i].fi); } dfs(1, 1); for (int i=1; i<=n; ++i)up(in[i], -1), up(out[i], 1); while (m--){ cin>>e; a=edges[e].fi; b=edges[e].se; if (twok[a][0]==b)swap(a, b); if (t[e]){ val[b]=pp[b]=val[par(a)]; up(in[b], -1); up(out[b], 1); } else{ val[par(a)]+=val[b]-pp[b]; up(in[b], 1); up(out[b], -1); } t[e]=!t[e]; } while (q--)cin>>a, cout<<val[par(a)]<<"\n"; }
#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...