제출 #937031

#제출 시각아이디문제언어결과실행 시간메모리
937031ParsaS동기화 (JOI13_synchronization)C++17
20 / 100
3817 ms262144 KiB
// In the name of God #include<bits/stdc++.h> using namespace std; #define pb push_back #define fi first #define se second #define mp make_pair typedef long long ll; const int N = 5e5 + 5; int n, m, q; vector<int> qr[N]; vector<pair<int, int> > adj[N]; bool mark[N]; int sz[N], ans[N]; int ver[N], E[N], szver, szE; void dfs_sz(int& v, int p, int i = -1) { sz[v] = 1; ver[szver++] = v; if (i >= 0) { for (int j = 0; j < (int)qr[i].size(); j++) E[szE++] = qr[i][j]; } for (auto& a : adj[v]) { if (!mark[a.fi] && a.fi != p) { dfs_sz(a.fi, v, a.se); sz[v] += sz[a.fi]; } } } int find_centroid(int v, int S, int p = 0) { for (auto [u, i] : adj[v]) { if (!mark[u] && u != p && sz[u] * 2 > S) { return find_centroid(u, S, v); } } return v; } inline int get(int val) { return lower_bound(E, E + szE, val) - E; } const int M = 1e8; vector<int> vec[N]; int T; pair<int*, int> st[M]; int stsz; int inf = 1e9; void rem(int S) { while (stsz > S) { *st[stsz-1].fi = st[stsz-1].se; stsz--; } } inline void SET(int& x, int y) { if (y > inf || x == y) return; //assert(stsz < M); st[stsz++] = mp(&x, x); x = y; } bool ISSUM; int lz[N << 2], seg[N << 2]; void shift(int v, int tl, int tr) { if (lz[v] == -1) return; if ((lz[v]==0 && ISSUM) || tl == tr) SET(seg[v], lz[v] * (tr - tl + 1)); if (tl < tr) { SET(lz[v<<1], lz[v]); SET(lz[v << 1 | 1], lz[v]); } SET(lz[v], -1); } void set_val(int l, int r, int val, int v = 1, int tl = 0, int tr = szE) { if (l > r) return; shift(v, tl, tr); if (tl > r || tr < l) return; if (tl >= l && tr <= r) { SET(lz[v], val); shift(v, tl, tr); return; } int mid = (tl + tr) >> 1; set_val(l, r, val, v << 1, tl, mid); set_val(l, r, val, v << 1 | 1, mid + 1, tr); SET(seg[v], seg[v << 1] + seg[v << 1 | 1]); } int query(int l, int r, int v = 1, int tl = 0, int tr = szE) { if (l > r) return 0; shift(v, tl, tr); if (tl > r || tr < l) return 0; if (tl >= l && tr <= r) { return seg[v]; } int mid = (tl + tr) >> 1; return query(l, r, v << 1, tl, mid) + query(l, r, v << 1 | 1, mid + 1, tr); } void dfs2(int v, int i, int p = 0) { int S = stsz; int prv = -1; for (int j = 0; j < (int)qr[i].size(); j += 2) { int x = get(qr[i][j]); set_val(get(prv + 1), x - 1, query(x, x)); prv = qr[i][j + 1]; } set_val(get(prv + 1), get(m + 1), inf); vec[T].pb(query(0, 0)); for (auto [u, j] : adj[v]) { if (mark[u] || u == p) continue; dfs2(u, j, v); } rem(S); } void dfs3(int v, int i, int p = 0) { int S = stsz; int prv = -1; for (int j = 0; j < (int)qr[i].size(); j += 2) { int x = get(qr[i][j]); int y = query(get(prv + 1), x - 1) + query(x, x); set_val(get(prv + 1), x - 1, 0); set_val(x, x, y); prv = qr[i][j + 1]; } set_val(get(prv + 1), get(m + 1), 0); ans[v] += query(0, get(m + 1)); for (auto [u, j] : adj[v]) { if (mark[u] || u == p) continue; dfs3(u, j, v); } rem(S); } void dfs(int v) { rem(0); szver = 0; szE = 0; E[szE++] = 0; E[szE++] = m + 1; E[szE++] = m + 2; dfs_sz(v, 0); int rt = find_centroid(v, sz[v]); mark[rt] = 1; sort(E, E + szE); szE = unique(E, E + szE) - E; int k = szE; for (int i = 0; i < k; i++) set_val(i, i, i); int S = stsz; for (auto [u, i] : adj[rt]) { if (mark[u]) continue; rem(S); T = u; vec[T].clear(); dfs2(u, i); } rem(0); ISSUM = true; set_val(0, 0, 1); for (auto [u, i] : adj[rt]) { if (mark[u]) continue; for (auto x : vec[u]) { if (x < inf) set_val(x, x, query(x, x) + 1); } } ans[rt] += query(0, m + 2); for (auto [u, i] : adj[rt]) { if (mark[u]) continue; S = stsz; for (auto x : vec[u]) if (x < inf) set_val(x, x, query(x, x) - 1); dfs3(u, i); rem(S); } ISSUM = false; for (auto [u, i] : adj[rt]) { if (!mark[u]) dfs(u); } } void solve() { cin >> n >> m >> q; for (int i = 1; i <= n - 1; i++) { int v, u; cin >> v >> u; adj[v].pb(mp(u, i)), adj[u].pb(mp(v, i)); } for (int i = 1; i <= m; i++) { int k; cin >> k; qr[k].pb(i); } for (int i = 1; i < n; i++) { if ((int)qr[i].size() % 2) qr[i].pb(m + 1); } memset(lz, -1, sizeof lz); dfs(1); while (q--) { int c; cin >> c; cout << ans[c] << '\n'; } } int32_t main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); //freopen("input2.in", "r", stdin); int tc = 1; // cin >> tc; while (tc--) { solve(); } 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...