oj.uz

Submission #630344

# Submission time Handle Problem Language Result Execution time Memory
630344 2022-08-16T08:31:55 Z Arnch Mergers (JOI19_mergers) C++17
0 / 100
 155 ms 98484 KB 
// oooo
/*
 har chi delet mikhad bebar ~
 gitar o ba khodet nabar! ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
//#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
//#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long double ld;

#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl
#define mak make_pair

//constexpr int PRI = 1000696969;
constexpr ll INF = 1e18, N = 1e6 + 10, MOD = 1e9 + 7, LOG = 20;

int s[N];
int par[N][LOG], h[N], st[N], fn[N], tim;
int sz[N], pv[N];
int ans;
vector<int> vc[N], adj[N], nei[N];

void dfs(int x, int p = -1) {
	par[x][0] = p;
	for(int i = 1; i < LOG; i++) par[x][i] = par[par[x][i - 1]][i - 1];
	h[x] = h[p] + 1;
	st[x] = tim++;
	for(auto j : adj[x]) {
		if(j == p) continue;
		dfs(j, x);
	}
	fn[x] = tim;
}
int get_par(int x, int y) {
	for(int i = 0; i < LOG; i++)
		if((y >> i) & 1)
			x = par[x][i];
	return x;
}
int lca(int x, int y) {
	if(h[x] > h[y]) swap(x, y);
	y = get_par(y, h[y] - h[x]);
	if(x == y) return x;
	for(int i = LOG - 1; i >= 0; i--)
		if(par[x][i] != par[y][i])
			x = par[x][i], y = par[y][i];
	return par[x][0];
}

int find(int x) {
	if(pv[x] == x) return x;
	return pv[x] = find(pv[x]);
}
void merge(int x, int y) {
	int X = find(x), Y = find(y);
	if(X == Y) return;
	if(sz[X] < sz[Y]) swap(X, Y);
	pv[Y] = X, sz[X] += sz[Y];
}

bool cmp(int i, int j) {
	return st[i] < st[j];
}
void solve(int x) {
	vector<int> ver;
	for(auto i : vc[x]) ver.push_back(i);
	sort(All(ver), cmp);
	int sz = Sz(ver);
	for(int i = 1; i < sz; i++) {
		ver.push_back(lca(ver[i - 1], ver[i]));
	}
	sort(All(ver), cmp);
	ver.erase(unique(All(ver)), ver.end());

	stack<int> mt;
	mt.push(ver[0]);

	merge(ver[0], x);
	for(int i = 1; i < Sz(ver); i++) {
		int v = ver[i];
		while(fn[mt.top()] < fn[v]) mt.pop();
		int p = mt.top();

		merge(x, v);
		v = par[v][0];
		while(v != p) {
			merge(x, v);
			v = par[v][0];
		}
		mt.push(v);
	}
}

int main() {
	ios :: sync_with_stdio(0), cin.tie(0); cout.tie(0);

	for(int i = 0; i < N; i++) sz[i] = 1, pv[i] = i;

	int n, k; cin >>n >>k;
	for(int i = 0; i < n - 1; i++) {
		int u, v; cin >>u >>v;
		--u, --v;
		adj[u].push_back(v), adj[v].push_back(u);
	}
	for(int i = 0; i < n; i++) {
		cin >>s[i];
		--s[i], s[i] += n;
		vc[s[i]].push_back(i);
	}

	dfs(0);

	for(int i = n; i < n + k; i++) {
		solve(i);
	}

	for(int i = 0; i < n; i++) {
		for(auto j : adj[i]) {
			if(pv[j] == pv[i]) continue;
			nei[pv[j]].push_back(pv[i]);
			nei[pv[i]].push_back(pv[j]);
		}
	}

	for(int i = 0; i < N; i++) {
		nei[i].erase(unique(All(nei[i])), nei[i].end());
		if(Sz(nei[i]) == 1) ans++;
	}
	cout<<(ans + 1) / 2;

	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 78548 KB Output is correct
2 Correct 40 ms 78652 KB Output is correct
3 Correct 41 ms 78620 KB Output is correct
4 Correct 41 ms 78540 KB Output is correct
5 Correct 41 ms 78632 KB Output is correct
6 Correct 40 ms 78540 KB Output is correct
7 Correct 41 ms 78512 KB Output is correct
8 Correct 41 ms 78628 KB Output is correct
9 Correct 41 ms 78616 KB Output is correct
10 Correct 41 ms 78548 KB Output is correct
11 Correct 42 ms 78540 KB Output is correct
12 Correct 42 ms 78600 KB Output is correct
13 Incorrect 41 ms 78548 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 78548 KB Output is correct
2 Correct 40 ms 78652 KB Output is correct
3 Correct 41 ms 78620 KB Output is correct
4 Correct 41 ms 78540 KB Output is correct
5 Correct 41 ms 78632 KB Output is correct
6 Correct 40 ms 78540 KB Output is correct
7 Correct 41 ms 78512 KB Output is correct
8 Correct 41 ms 78628 KB Output is correct
9 Correct 41 ms 78616 KB Output is correct
10 Correct 41 ms 78548 KB Output is correct
11 Correct 42 ms 78540 KB Output is correct
12 Correct 42 ms 78600 KB Output is correct
13 Incorrect 41 ms 78548 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 78548 KB Output is correct
2 Correct 40 ms 78652 KB Output is correct
3 Correct 41 ms 78620 KB Output is correct
4 Correct 41 ms 78540 KB Output is correct
5 Correct 41 ms 78632 KB Output is correct
6 Correct 40 ms 78540 KB Output is correct
7 Correct 41 ms 78512 KB Output is correct
8 Correct 41 ms 78628 KB Output is correct
9 Correct 41 ms 78616 KB Output is correct
10 Correct 41 ms 78548 KB Output is correct
11 Correct 42 ms 78540 KB Output is correct
12 Correct 42 ms 78600 KB Output is correct
13 Incorrect 41 ms 78548 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 92096 KB Output is correct
2 Correct 139 ms 98484 KB Output is correct
3 Correct 44 ms 79116 KB Output is correct
4 Correct 50 ms 79024 KB Output is correct
5 Correct 41 ms 78628 KB Output is correct
6 Correct 41 ms 78636 KB Output is correct
7 Correct 43 ms 78908 KB Output is correct
8 Incorrect 155 ms 93240 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 78548 KB Output is correct
2 Correct 40 ms 78652 KB Output is correct
3 Correct 41 ms 78620 KB Output is correct
4 Correct 41 ms 78540 KB Output is correct
5 Correct 41 ms 78632 KB Output is correct
6 Correct 40 ms 78540 KB Output is correct
7 Correct 41 ms 78512 KB Output is correct
8 Correct 41 ms 78628 KB Output is correct
9 Correct 41 ms 78616 KB Output is correct
10 Correct 41 ms 78548 KB Output is correct
11 Correct 42 ms 78540 KB Output is correct
12 Correct 42 ms 78600 KB Output is correct
13 Incorrect 41 ms 78548 KB Output isn't correct
14 Halted 0 ms 0 KB -