Submission #1355501

#TimeUsernameProblemLanguageResultExecution timeMemory
1355501blackscreen1Synchronization (JOI13_synchronization)C++20
100 / 100
350 ms32620 KiB
#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_multiset;
#define ll long long
#define iloop(m, h) for (auto i = m; i != h; i += (m < h ? 1 : -1))
#define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1))
#define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1))
#define lloop(m, h) for (auto l = m; l != h; l += (m < h ? 1 : -1))
#define pll pair<ll, ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
ll n, m, q, x, p1, p2, xp;
vector<ll> adj[100005];
pll edg[100005];
bool act[100005];
ll pre[100005], pos[100005], cnt = 0;
ll a[100005], b[100005];
ll twok[20][100005];
void dfs(ll nd, ll pr) {
	twok[0][nd] = pr;
	iloop(1, 20) {
		if (twok[i-1][nd] == -1) break;
		twok[i][nd] = twok[i-1][twok[i-1][nd]];
	}
	pre[nd] = cnt++;
	for (auto it : adj[nd]) if (it != pr) dfs(it, nd);
	pos[nd] = cnt - 1;
}
ll seg[200005];
void upd(ll L, ll R, ll V) {
	R++;
	for (L += n, R += n; L < R; L >>= 1, R >>= 1) {
		if (L&1) seg[L++] += V;
		if (R&1) seg[--R] += V;
	}
}
ll qu(ll X) {
	ll res = 0;
	for (X += n; X > 0; X >>= 1) res += seg[X];
	return res;
}
ll fp(ll nd) {
	ll tr = qu(pre[nd]);
	iloop(19, -1) if (twok[i][nd] != -1 && qu(pre[twok[i][nd]]) == tr) nd = twok[i][nd];
	return nd;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	memset(twok, -1, sizeof(twok));
	cin >> n >> m >> q;
	iloop(1, n) {
		cin >> edg[i].first >> edg[i].second;
		edg[i].first--, edg[i].second--;
		adj[edg[i].first].push_back(edg[i].second);
		adj[edg[i].second].push_back(edg[i].first);
	}
	iloop(0, n) a[i] = 1;
	dfs(0, -1);
	iloop(1, n) upd(pre[i], pos[i], 1);
	iloop(0, m) {
		cin >> x;
		if (pre[edg[x].first] < pre[edg[x].second]) p1 = edg[x].first, p2 = edg[x].second;
		else p1 = edg[x].second, p2 = edg[x].first;
		if (!act[x]) {
			xp = fp(p1);
			a[xp] += a[p2] - b[p2];
			upd(pre[p2], pos[p2], -1);
		}
		else {
			xp = fp(p1);
			a[p2] = b[p2] = a[xp];
			upd(pre[p2], pos[p2], 1);
		}
		act[x] ^= 1;
	}
	ll ans[n];
	iloop(0, n) ans[i] = a[fp(i)];
	while (q--) {cin >> x; cout << ans[x-1] << "\n";}
}
#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...