oj.uz

Submission #936737

# Submission time Handle Problem Language Result Execution time Memory
936737 2024-03-02T16:18:48 Z ParsaS Synchronization (JOI13_synchronization) C++17
0 / 100
 6200 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()) {
	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);
	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 21852 KB Output is correct
3 Correct 5 ms 21848 KB Output is correct
4 Correct 5 ms 21852 KB Output is correct
5 Correct 6 ms 21884 KB Output is correct
6 Correct 26 ms 22568 KB Output is correct
7 Correct 383 ms 31244 KB Output is correct
8 Correct 393 ms 33032 KB Output is correct
9 Correct 402 ms 31940 KB Output is correct
10 Correct 5749 ms 102776 KB Output is correct
11 Correct 6079 ms 104772 KB Output is correct
12 Runtime error 321 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 304 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 5 ms 21852 KB Output is correct
3 Correct 7 ms 22132 KB Output is correct
4 Correct 7 ms 22108 KB Output is correct
5 Correct 6 ms 22108 KB Output is correct
6 Correct 42 ms 27852 KB Output is correct
7 Correct 667 ms 90020 KB Output is correct
8 Runtime error 306 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 301 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 4 ms 21848 KB Output is correct
2 Correct 5 ms 21852 KB Output is correct
3 Correct 4 ms 21852 KB Output is correct
4 Correct 6 ms 22108 KB Output is correct
5 Correct 26 ms 22484 KB Output is correct
6 Correct 388 ms 32012 KB Output is correct
7 Correct 6200 ms 102984 KB Output is correct
8 Runtime error 300 ms 262144 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -