oj.uz

Submission #630341

# Submission time Handle Problem Language Result Execution time Memory
630341 2022-08-16T08:14:45 Z Arnch Mergers (JOI19_mergers) C++17
0 / 100
 155 ms 100232 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;
	ans--;
	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]);
		}
	}

	int ans = 0;
	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 37 ms 78544 KB Output is correct
2 Correct 39 ms 78612 KB Output is correct
3 Correct 39 ms 78516 KB Output is correct
4 Correct 40 ms 78536 KB Output is correct
5 Correct 38 ms 78600 KB Output is correct
6 Correct 37 ms 78648 KB Output is correct
7 Correct 39 ms 78652 KB Output is correct
8 Correct 40 ms 78716 KB Output is correct
9 Correct 42 ms 78524 KB Output is correct
10 Correct 40 ms 78648 KB Output is correct
11 Correct 45 ms 78520 KB Output is correct
12 Correct 39 ms 78620 KB Output is correct
13 Incorrect 39 ms 78600 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 78544 KB Output is correct
2 Correct 39 ms 78612 KB Output is correct
3 Correct 39 ms 78516 KB Output is correct
4 Correct 40 ms 78536 KB Output is correct
5 Correct 38 ms 78600 KB Output is correct
6 Correct 37 ms 78648 KB Output is correct
7 Correct 39 ms 78652 KB Output is correct
8 Correct 40 ms 78716 KB Output is correct
9 Correct 42 ms 78524 KB Output is correct
10 Correct 40 ms 78648 KB Output is correct
11 Correct 45 ms 78520 KB Output is correct
12 Correct 39 ms 78620 KB Output is correct
13 Incorrect 39 ms 78600 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 78544 KB Output is correct
2 Correct 39 ms 78612 KB Output is correct
3 Correct 39 ms 78516 KB Output is correct
4 Correct 40 ms 78536 KB Output is correct
5 Correct 38 ms 78600 KB Output is correct
6 Correct 37 ms 78648 KB Output is correct
7 Correct 39 ms 78652 KB Output is correct
8 Correct 40 ms 78716 KB Output is correct
9 Correct 42 ms 78524 KB Output is correct
10 Correct 40 ms 78648 KB Output is correct
11 Correct 45 ms 78520 KB Output is correct
12 Correct 39 ms 78620 KB Output is correct
13 Incorrect 39 ms 78600 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 93500 KB Output is correct
2 Correct 135 ms 100232 KB Output is correct
3 Correct 43 ms 79084 KB Output is correct
4 Correct 44 ms 78976 KB Output is correct
5 Correct 50 ms 78624 KB Output is correct
6 Correct 42 ms 78620 KB Output is correct
7 Correct 40 ms 79060 KB Output is correct
8 Incorrect 155 ms 95080 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 78544 KB Output is correct
2 Correct 39 ms 78612 KB Output is correct
3 Correct 39 ms 78516 KB Output is correct
4 Correct 40 ms 78536 KB Output is correct
5 Correct 38 ms 78600 KB Output is correct
6 Correct 37 ms 78648 KB Output is correct
7 Correct 39 ms 78652 KB Output is correct
8 Correct 40 ms 78716 KB Output is correct
9 Correct 42 ms 78524 KB Output is correct
10 Correct 40 ms 78648 KB Output is correct
11 Correct 45 ms 78520 KB Output is correct
12 Correct 39 ms 78620 KB Output is correct
13 Incorrect 39 ms 78600 KB Output isn't correct
14 Halted 0 ms 0 KB -