Submission #1265823

#TimeUsernameProblemLanguageResultExecution timeMemory
1265823icebearSynchronization (JOI13_synchronization)C++20
100 / 100
202 ms26116 KiB
// ~~ icebear ~~ #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> ii; typedef pair<int, ii> iii; template<class T> bool minimize(T &a, const T &b) { if (a > b) return a = b, true; return false; } template<class T> bool maximize(T &a, const T &b) { if (a < b) return a = b, true; return false; } #define FOR(i,a,b) for(int i=(a); i<=(b); ++i) #define FORR(i,a,b) for(int i=(a); i>=(b); --i) #define REP(i, n) for(int i=0; i<(n); ++i) #define RED(i, n) for(int i=(n)-1; i>=0; --i) #define MASK(i) (1LL << (i)) #define BIT(S, i) (((S) >> (i)) & 1) #define mp make_pair #define pb push_back #define fi first #define se second #define all(x) x.begin(), x.end() #define task "icebear" const int MOD = 1e9 + 7; const int inf = 1e9 + 27092008; const ll INF = 1e18 + 27092008; const int N = 2e5 + 5; int n, m, q; vector<int> G[N]; int par[N][20], h[N]; int tin[N], tout[N], timer = 0; ii edge[N]; int ft[N]; void update(int x, int v) { for(; x <= n; x += x & -x) ft[x] += v; } int get(int x) { int ans = 0; for(; x; x -= x & -x) ans += ft[x]; return ans; } int root(int u) { RED(j, 20) if (par[u][j] > 0) { int tmp = get(tin[u]) - get(tin[par[u][j]]); if (!tmp) u = par[u][j]; } return u; } void dfs(int u) { tin[u] = ++timer; for(int v : G[u]) { if (v == par[u][0]) continue; par[v][0] = u; h[v] = h[u] + 1; dfs(v); } tout[u] = timer; } void init(void) { cin >> n >> m >> q; FOR(i, 2, n) { int u, v; cin >> u >> v; G[u].pb(v); G[v].pb(u); edge[i - 1] = mp(u, v); } } void process(void) { dfs(1); FOR(j, 1, 19) FOR(i, 1, n) par[i][j] = par[par[i][j - 1]][j - 1]; FOR(i, 1, n - 1) { if (h[edge[i].fi] > h[edge[i].se]) swap(edge[i].fi, edge[i].se); update(tin[edge[i].se], +1); update(tout[edge[i].se] + 1, -1); } vector<bool> state(n, false); vector<int> last_contribute(n + 5, 0); vector<int> ans(n + 5, 1); while(m--) { int e; cin >> e; int u, v; tie(u, v) = edge[e]; update(tin[v], (state[e] ? +1 : -1)); update(tout[v] + 1, (state[e] ? -1 : +1)); if (state[e] == false) { ans[root(v)] += ans[v] - last_contribute[v]; } else { last_contribute[v] = ans[v] = ans[root(u)]; } state[e] = state[e] ^ 1; } while(q--) { int u; cin >> u; cout << ans[root(u)] << '\n'; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } int tc = 1; // cin >> tc; while(tc--) { init(); process(); } return 0; }

Compilation message (stderr)

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