제출 #1257846

#제출 시각아이디문제언어결과실행 시간메모리
1257846nai0610동기화 (JOI13_synchronization)C++20
100 / 100
230 ms23624 KiB
#include <bits/stdc++.h> #define ll int64_t #define ld long double using namespace std; // const int maxn =1e5+5; const int mod = 1e9+7; // 998244353,1610612741 const ll inf = 1e18; const ld pi = atan(1.0L)*4; int n,m,q,tin[maxn],tout[maxn],cur; pair<int,int> e[maxn]; vector<int> g[maxn]; int h[maxn],st[maxn][20]; int bit[maxn],res[maxn],pre[maxn]; bool has[maxn]; void update(int i,int x) { for (;i<=n;i+=i&-i) bit[i]+=x; } int query(int i){ int res=0; for (;i>0;i-=i&-i) res+=bit[i]; return res; } void dfs(int u){ tin[u]=++cur; for (auto v:g[u]) { if (st[u][0]==v) continue; h[v]=h[u]+1; st[v][0]=u; for (int i=1;i<=17;i++) st[v][i]=st[st[v][i-1]][i-1]; dfs(v); } tout[u]=cur; } int calc(int u){ int cur=query(tin[u]); for (int i=17;i>=0;i--) { int val=query(tin[st[u][i]]); if ((cur-val)&(1<<i)) { cur=val; u=st[u][i]; } } return u; } void up(int id) { int u=e[id].first,v=e[id].second; if (h[u]>h[v]) swap(u,v); int w=calc(u); if (!has[id]) { res[w]+=res[v]-pre[v]; update(tin[v],1); update(tout[v]+1,-1); } else{ res[v]=pre[v]=res[w]; update(tin[v],-1); update(tout[v]+1,1); } has[id]^=1; } int main() { // freopen("../input.inp","r",stdin); // freopen("output.out","w",stdout); ios::sync_with_stdio(false); cin.tie(nullptr); clock_t start,end; start=clock(); cin>>n>>m>>q; for (int i=1;i<=n;i++) res[i]=1; for (int i=1;i<n;i++) { int u,v; cin >>u>>v; e[i]={u,v}; g[u].push_back(v); g[v].push_back(u); } dfs(1); while (m--) { int id; cin >>id; up(id); } for (int i=1;i<n;i++) { if (has[i]) up(i); } while (q--) { int u;cin >>u; cout <<res[u]<<'\n'; } end=clock(); ld dur=(ld)(end-start)/(ld)(CLOCKS_PER_SEC)*(1000.0L); cerr<<dur<<'\n'; return 0; }
#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...