oj.uz

Submission #937028

# Submission time Handle Problem Language Result Execution time Memory
937028 2024-03-03T09:05:08 Z ParsaS Synchronization (JOI13_synchronization) C++17
20 / 100
 3925 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];
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 = 3e7;
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 5 ms 23644 KB Output is correct
2 Correct 5 ms 23644 KB Output is correct
3 Correct 6 ms 23688 KB Output is correct
4 Correct 5 ms 23644 KB Output is correct
5 Correct 6 ms 23720 KB Output is correct
6 Correct 21 ms 25772 KB Output is correct
7 Correct 233 ms 31336 KB Output is correct
8 Correct 225 ms 31336 KB Output is correct
9 Correct 263 ms 31460 KB Output is correct
10 Correct 3688 ms 97596 KB Output is correct
11 Correct 3862 ms 97308 KB Output is correct
12 Runtime error 308 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 2444 ms 155080 KB Output is correct
2 Correct 2363 ms 153724 KB Output is correct
3 Correct 3439 ms 174172 KB Output is correct
4 Correct 3620 ms 174216 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 23640 KB Output is correct
2 Correct 5 ms 23644 KB Output is correct
3 Correct 7 ms 25692 KB Output is correct
4 Correct 7 ms 25788 KB Output is correct
5 Correct 5 ms 23644 KB Output is correct
6 Correct 30 ms 25952 KB Output is correct
7 Correct 397 ms 46692 KB Output is correct
8 Runtime error 298 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 348 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 5 ms 23644 KB Output is correct
2 Correct 5 ms 23644 KB Output is correct
3 Correct 5 ms 23644 KB Output is correct
4 Correct 6 ms 25692 KB Output is correct
5 Correct 19 ms 25692 KB Output is correct
6 Correct 249 ms 31440 KB Output is correct
7 Correct 3925 ms 98516 KB Output is correct
8 Runtime error 295 ms 262144 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -