Submission #887527

#TimeUsernameProblemLanguageResultExecution timeMemory
887527AgentPenginSynchronization (JOI13_synchronization)C++17
100 / 100
224 ms25356 KiB
/** * author: AgentPengin ( Độc cô cầu bại ) * created: 23.12.2022 10:08:02 * too lazy to update time **/ #include<bits/stdc++.h> #define EL '\n' #define fi first #define se second #define NAME "TASK" #define ll long long #define lcm(a,b) (a/gcd(a,b))*b #define db(val) "["#val" = " << (val) << "] " #define bend(v) (v).begin(),(v).end() #define sz(v) (int)(v).size() #define ex exit(0) using namespace std; const ll mod = 1e9 + 7; const int inf = 0x1FFFFFFF; const int MAXN = 1e5 + 5; int n,m,q; vector<int> adj[MAXN]; pair<int,int> edges[MAXN << 1]; bool active[MAXN]; int info[MAXN],last_sync[MAXN]; int times = 1,tin[MAXN],tout[MAXN]; int up[MAXN][20]; void dfs(int u = 1,int p = 0) { up[u][0] = p; for (int i = 1;i < 20 && up[u][i - 1];i++) { up[u][i] = up[up[u][i - 1]][i - 1]; } info[u] = 1; tin[u] = times++; for (auto v : adj[u]) if (v != p) dfs(v,u); tout[u] = times; } int bit[MAXN]; void update(int x,int val) { for (;x <= n;x += x&-x) bit[x] += val; } int get(int x) { int res = 0; for (;x;x-=x&-x) res += bit[x]; return res; } int find_anc(int u) { int lca = u; for (int i = 19; ~ i;i--) { if (up[lca][i] && get(tin[up[lca][i]]) == get(tin[u])) lca = up[lca][i]; } return lca; } signed main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); if (ifstream(NAME".inp")) { freopen(NAME".inp","r",stdin); freopen(NAME".out","w",stdout); } cin >> n >> m >> q; for (int i = 1;i < n;i++) { cin >> edges[i].fi >> edges[i].se; adj[edges[i].fi].push_back(edges[i].se); adj[edges[i].se].push_back(edges[i].fi); } dfs(); for (int i = 1;i <= n;i++) { update(tin[i],-1); update(tout[i],1); } while(m--) { int x; cin >> x; int u = edges[x].fi,v = edges[x].se; if (up[u][0] == v) swap(u,v); if (active[x]) { info[v] = last_sync[v] = info[find_anc(u)]; update(tin[v],-1); update(tout[v],1); } else { info[find_anc(u)] += info[v] - last_sync[v]; update(tin[v],1); update(tout[v],-1); } active[x] = !active[x]; } while(q--) { int x; cin >> x; cout << info[find_anc(x)] << EL; } cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n"; return 0; } // agent pengin wants to take apio (with anya-san)

Compilation message (stderr)

synchronization.cpp: In function 'int main()':
synchronization.cpp:69:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         freopen(NAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         freopen(NAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#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...