Submission #936745

#	Time	Username	Problem	Language	Result	Execution time	Memory
936745		ParsaS	Synchronization (JOI13_synchronization)	C++17	20 / 100	4054 ms	262144 KiB

synchronization

// 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 = 1e6 + 5;
int n, m, q;
vector<int> qr[N];
vector<pair<int, int> > adj[N];
pair<int, int> edg[N];
bool mark[N];
int sz[N], ans[N];
vector<int> ver, E;

void dfs_sz(int v, int p = 0) {
	sz[v] = 1;
	ver.pb(v);
	for (auto [u, i] : adj[v]) {
		if (!mark[u] && u != p) {
			for (auto x : qr[i])
				E.pb(x);
			dfs_sz(u, v);
			sz[v] += sz[u];
		}
	}
}

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;
}

int get(int val) {
	return lower_bound(E.begin(), E.end(), val) - E.begin();
}

vector<int> vec[N];
int T;
pair<int*, int> st[N << 4];
int stsz;
int inf = 1e9;

void rem(int S) {
	while (stsz > S) {
		*st[stsz-1].fi = st[stsz-1].se;
		stsz--;
	}
}
void SET(int& x, int y) {
	if (y > inf) return;
	st[stsz++] = mp(&x, x);
	x = y;
}

int lz[N << 2], seg[N << 2];


void shift(int v, int tl, int tr) {
	if (lz[v] == -1) return;
	if (lz[v]==0 || 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 = E.size()) {
	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 = E.size()) {
	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);
	ver.clear();
	E.clear();
	E.pb(0);
	E.pb(m + 1);
	E.pb(m + 2);
	dfs_sz(v);
	int rt = find_centroid(v, sz[v]);
	mark[rt] = 1;

	sort(E.begin(), E.end());
	E.resize(unique(E.begin(), E.end()) - E.begin());

	int k = E.size();

	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);
	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);
	}

	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));
		edg[i] = mp(v, u);
	}
	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);

	int tc = 1; // cin >> tc;
	while (tc--) {
		solve();
	}

	return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40