oj.uz

Submission #630343

# Submission time Handle Problem Language Result Execution time Memory
630343 2022-08-16T08:17:15 Z Arnch Mergers (JOI19_mergers) C++17
0 / 100
 171 ms 98532 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 + k; 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 78548 KB Output is correct
2 Correct 41 ms 78544 KB Output is correct
3 Correct 37 ms 78636 KB Output is correct
4 Correct 45 ms 78604 KB Output is correct
5 Correct 39 ms 78540 KB Output is correct
6 Correct 38 ms 78540 KB Output is correct
7 Correct 37 ms 78588 KB Output is correct
8 Correct 42 ms 78676 KB Output is correct
9 Correct 41 ms 78540 KB Output is correct
10 Correct 38 ms 78536 KB Output is correct
11 Correct 38 ms 78568 KB Output is correct
12 Correct 37 ms 78592 KB Output is correct
13 Incorrect 42 ms 78580 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 78548 KB Output is correct
2 Correct 41 ms 78544 KB Output is correct
3 Correct 37 ms 78636 KB Output is correct
4 Correct 45 ms 78604 KB Output is correct
5 Correct 39 ms 78540 KB Output is correct
6 Correct 38 ms 78540 KB Output is correct
7 Correct 37 ms 78588 KB Output is correct
8 Correct 42 ms 78676 KB Output is correct
9 Correct 41 ms 78540 KB Output is correct
10 Correct 38 ms 78536 KB Output is correct
11 Correct 38 ms 78568 KB Output is correct
12 Correct 37 ms 78592 KB Output is correct
13 Incorrect 42 ms 78580 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 78548 KB Output is correct
2 Correct 41 ms 78544 KB Output is correct
3 Correct 37 ms 78636 KB Output is correct
4 Correct 45 ms 78604 KB Output is correct
5 Correct 39 ms 78540 KB Output is correct
6 Correct 38 ms 78540 KB Output is correct
7 Correct 37 ms 78588 KB Output is correct
8 Correct 42 ms 78676 KB Output is correct
9 Correct 41 ms 78540 KB Output is correct
10 Correct 38 ms 78536 KB Output is correct
11 Correct 38 ms 78568 KB Output is correct
12 Correct 37 ms 78592 KB Output is correct
13 Incorrect 42 ms 78580 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 92136 KB Output is correct
2 Correct 171 ms 98532 KB Output is correct
3 Correct 42 ms 79032 KB Output is correct
4 Correct 46 ms 78908 KB Output is correct
5 Correct 38 ms 78548 KB Output is correct
6 Correct 38 ms 78540 KB Output is correct
7 Correct 39 ms 79016 KB Output is correct
8 Incorrect 155 ms 93480 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 78548 KB Output is correct
2 Correct 41 ms 78544 KB Output is correct
3 Correct 37 ms 78636 KB Output is correct
4 Correct 45 ms 78604 KB Output is correct
5 Correct 39 ms 78540 KB Output is correct
6 Correct 38 ms 78540 KB Output is correct
7 Correct 37 ms 78588 KB Output is correct
8 Correct 42 ms 78676 KB Output is correct
9 Correct 41 ms 78540 KB Output is correct
10 Correct 38 ms 78536 KB Output is correct
11 Correct 38 ms 78568 KB Output is correct
12 Correct 37 ms 78592 KB Output is correct
13 Incorrect 42 ms 78580 KB Output isn't correct
14 Halted 0 ms 0 KB -