제출 #1261713

#제출 시각아이디문제언어결과실행 시간메모리
12617134o2aSynchronization (JOI13_synchronization)C++20
100 / 100
183 ms37408 KiB
#include <bits/stdc++.h> #define pb push_back #define fi first #define se second #define _F "what" using namespace std; typedef long long ll; constexpr int N = 1e5 + 1, M = 2e5 + 1; int n, m, q; vector<int> par(N, -1), sz(N, 1), lab(N, 1), pre(N), st[4*M], Q, L(N); pair<int, int> E[N]; stack<pair<int, int>> rb; int find_set(int u) { return (par[u] == -1 ? u : find_set(par[u])); } void merge_set(int i) { int u = find_set(E[i].fi), v = find_set(E[i].se); if (u == v) { rb.push({-1, -1}); return; } else { if (sz[u] < sz[v]) swap(u, v); int new_lab = lab[u] + lab[v] - pre[i]; lab[u] = new_lab; par[v] = u; sz[u] += sz[v]; rb.push({v, i}); } } void rollback() { auto p = rb.top(); rb.pop(); int v = p.fi, i = p.se; if (v == -1) return; int u = par[v]; lab[v] = pre[i] = lab[u]; par[v] = -1; sz[u] -= sz[v]; } void add(int i, int l, int r, int tl = 1, int tr = m, int v = 1) { if (l > r) return; if (tl == l && tr == r) st[v].pb(i); else { int tm = (tl+tr)/2; add(i, l, min(tm, r), tl, tm, 2*v); add(i, max(l, tm+1), r, tm+1, tr, 2*v+1); } } void dfs_st(int tl = 1, int tr = m, int v = 1) { for (int i: st[v]) merge_set(i); if (tl == tr && tl == m) for (int u: Q) cout<<lab[find_set(u)]<<"\n"; else if (tl != tr) { int tm = (tl+tr)/2; dfs_st(tl, tm, 2*v); dfs_st(tm+1, tr, 2*v+1); } for (int i = 0; i < st[v].size(); ++i) rollback(); } void solve() { cin>>n>>m>>q; Q.resize(q); for (int i = 1; i < n; ++i) cin>>E[i].fi>>E[i].se; for (int i = 1; i <= m; ++i) { int x; cin>>x; if (L[x] > 0) { add(x, L[x], i-1); L[x] = 0; } else L[x] = i; } for (int i = 1; i < n; ++i) if (L[i] > 0) add(i, L[i], m); for (int i = 0; i < q; ++i) cin>>Q[i]; dfs_st(); } int main() { if (fopen(_F".INP", "r")) { freopen(_F".INP", "r", stdin); freopen(_F".OUT", "w", stdout); } else if (fopen("test.inp", "r")) { freopen("test.inp", "r", stdin); //freopen("test.out", "w", stdout); } ios_base::sync_with_stdio(0); cin.tie(0); int Test = 1; //cin>>Test; while (Test--) solve(); }

컴파일 시 표준 에러 (stderr) 메시지

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