Submission #995390

#TimeUsernameProblemLanguageResultExecution timeMemory
995390cpptowinSynchronization (JOI13_synchronization)C++17
100 / 100
250 ms64584 KiB
#include <bits/stdc++.h> #define fo(i, d, c) for (int i = d; i <= c; i++) #define fod(i, c, d) for (int i = c; i >= d; i--) #define maxn 1000010 #define N 1010 #define fi first #define se second #define pb emplace_back #define en cout << "\n"; #define int long long #define inf (int)1e18 #define pii pair<int, int> #define vii vector<pii> #define lb(x) x & -x #define bit(i, j) ((i >> j) & 1) #define offbit(i, j) (i ^ (1LL << j)) #define onbit(i, j) (i | (1LL << j)) #define vi vector<int> template <typename T1, typename T2> bool minimize(T1 &a, T2 b) { if (a > b) { a = b; return true; } return false; } template <typename T1, typename T2> bool maximize(T1 &a, T2 b) { if (a < b) { a = b; return true; } return false; } using namespace std; const int nsqrt = 450; const int mod = 1e9 + 7; int n,m,q; vi ke[maxn]; struct BIT { int t[maxn]; void up(int x,int val) { for( ; x < maxn ; x += lb(x)) t[x] += val; } void up(int l,int r,int val) { up(l,val); up(r + 1,-val); } int get(int x) { int ans = 0; for( ; x ; x -= lb(x)) ans += t[x]; return ans; } }t; int cnt,pos[maxn],tail[maxn],par[maxn][20]; void dfs(int u) { pos[u] = ++cnt; for(int v : ke[u]) if(v != par[u][0]) { par[v][0] = u; dfs(v); } tail[u] = cnt; } int find(int u) { fod(i,19,0) if(t.get(pos[u]) == t.get(pos[par[u][i]])) u = par[u][i]; return u; } int save[maxn]; bool on[maxn]; pii edge[maxn]; int res[maxn]; main() { #define name "TASK" if (fopen(name ".inp", "r")) { freopen(name ".inp", "r", stdin); freopen(name ".out", "w", stdout); } ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m >> q; fo(i,1,n - 1) { int u,v; cin >> u >> v; ke[u].pb(v); ke[v].pb(u); edge[i] = {u,v}; } dfs(1); fo(j,1,19) fo(i,1,n) par[i][j] = par[par[i][j - 1]][j - 1]; fo(i,1,n) t.up(pos[i],tail[i],1); fo(i,1,n) res[i] = 1; fo(i,1,m) { int id; cin >> id; auto [u,v] = edge[id]; if(pos[u] > pos[v]) swap(u,v); u = find(u); if(!on[id]) { res[u] = res[u] + res[v] - save[id]; t.up(pos[v],tail[v],-1); } else { res[v] = save[id] = res[u]; t.up(pos[v],tail[v],1); } on[id] = 1 - on[id]; } fo(i,1,q) { int x; cin >> x; cout << res[find(x)];en; } }

Compilation message (stderr)

synchronization.cpp:83:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   83 | main()
      | ^~~~
synchronization.cpp: In function 'int main()':
synchronization.cpp:88:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         freopen(name ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:89:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         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...