oj.uz

Submission #936738

# Submission time Handle Problem Language Result Execution time Memory
936738 2024-03-02T16:21:16 Z ParsaS Synchronization (JOI13_synchronization) C++17
0 / 100
 6345 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 = 2e5 + 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;
vector<pair<int*, int> > st;
int inf = 1e9;

void rem(int S) {
	while ((int)st.size() > S) {
		*st.back().fi = st.back().se;
		st.pop_back();
	}
}
void SET(int& x, int y) {
	st.pb(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;
	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 = st.size();
	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 = st.size();
	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 = st.size();

	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 = st.size();

		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.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21848 KB Output is correct
2 Correct 6 ms 21848 KB Output is correct
3 Correct 5 ms 21852 KB Output is correct
4 Correct 5 ms 21852 KB Output is correct
5 Correct 6 ms 21852 KB Output is correct
6 Correct 26 ms 22488 KB Output is correct
7 Correct 381 ms 31252 KB Output is correct
8 Correct 404 ms 32004 KB Output is correct
9 Correct 398 ms 32008 KB Output is correct
10 Correct 5894 ms 102660 KB Output is correct
11 Correct 6165 ms 102616 KB Output is correct
12 Runtime error 295 ms 262144 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21852 KB Output is correct
2 Correct 4 ms 21932 KB Output is correct
3 Correct 7 ms 22128 KB Output is correct
4 Correct 6 ms 22108 KB Output is correct
5 Correct 6 ms 21876 KB Output is correct
6 Correct 42 ms 26812 KB Output is correct
7 Correct 669 ms 91780 KB Output is correct
8 Runtime error 301 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 289 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 6 ms 21848 KB Output is correct
2 Correct 4 ms 21852 KB Output is correct
3 Correct 5 ms 21852 KB Output is correct
4 Correct 6 ms 22104 KB Output is correct
5 Correct 26 ms 22488 KB Output is correct
6 Correct 396 ms 32524 KB Output is correct
7 Correct 6345 ms 102724 KB Output is correct
8 Runtime error 299 ms 262144 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -