oj.uz

Submission #937031

# Submission time Handle Problem Language Result Execution time Memory
937031 2024-03-03T09:08:16 Z ParsaS Synchronization (JOI13_synchronization) C++17
20 / 100
 3817 ms 262144 KB 
// 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;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 55128 KB Output is correct
2 Correct 11 ms 55128 KB Output is correct
3 Correct 12 ms 55132 KB Output is correct
4 Correct 11 ms 55132 KB Output is correct
5 Correct 13 ms 55244 KB Output is correct
6 Correct 25 ms 55180 KB Output is correct
7 Correct 240 ms 62572 KB Output is correct
8 Correct 235 ms 63060 KB Output is correct
9 Correct 250 ms 62800 KB Output is correct
10 Correct 3462 ms 124872 KB Output is correct
11 Correct 3623 ms 124956 KB Output is correct
12 Runtime error 282 ms 262144 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2221 ms 182072 KB Output is correct
2 Correct 2169 ms 180448 KB Output is correct
3 Correct 3304 ms 201584 KB Output is correct
4 Correct 3403 ms 196304 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 48984 KB Output is correct
2 Correct 13 ms 48988 KB Output is correct
3 Correct 15 ms 48984 KB Output is correct
4 Correct 14 ms 55132 KB Output is correct
5 Correct 16 ms 55132 KB Output is correct
6 Correct 39 ms 45660 KB Output is correct
7 Correct 403 ms 65456 KB Output is correct
8 Runtime error 310 ms 262144 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 313 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 43864 KB Output is correct
2 Correct 18 ms 43868 KB Output is correct
3 Correct 18 ms 43868 KB Output is correct
4 Correct 23 ms 44152 KB Output is correct
5 Correct 31 ms 44632 KB Output is correct
6 Correct 246 ms 50960 KB Output is correct
7 Correct 3817 ms 116644 KB Output is correct
8 Runtime error 279 ms 262144 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -