oj.uz

Submission #1039914

# Submission time Handle Problem Language Result Execution time Memory
1039914 2024-07-31T12:19:19 Z ymm Capital City (JOI20_capital_city) C++17
100 / 100
 690 ms 272780 KB 
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 200'010;
const int lg = 20;

struct snode;
struct gnode;

struct gnode {
	gnode *par;
	gnode *anc[lg];
	vector<gnode *> adj;
	gnode *hchild, *hroot, *hleaf;
	snode *sroot;
	int st, ft, ht;
	int col;

	int sz() { return ft - st; }
	int hsz() { return hleaf->ht - hroot->ht + 1; }
} graph[N];

struct snode {
	vector<snode *> adj;
	vector<snode *> adjt;
	int weight;
	int vis;

	static void add_edge(snode *v, snode *u) {
		v->adj.push_back(u);
		u->adjt.push_back(v);
	}
} pool[(1<<28) / sizeof(gnode)];

vector<snode *> all_snodes;

snode *new_snode()
{
	static int p = 0;
	all_snodes.push_back(&pool[p]);
	return &pool[p++];
}

void dfsg1(gnode *v, gnode *p, int &t, int h)
{
	v->par = p;
	v->st = t++;
	v->ht = h;

	v->anc[0] = v->par? v->par: v;
	Loop (i,0,lg-1)
		v->anc[i + 1] = v->anc[i]->anc[i];

	for (auto u : v->adj)
		if (u != p)
			dfsg1(u, v, t, h + 1);
	v->ft = t++;
	for (auto u : v->adj) {
		if (u == p)
			continue;
		if (v->hchild == 0 || v->hchild->sz() < u->sz())
			v->hchild = u;
	}
}

gnode *lca(gnode *v, gnode *u)
{
	if (v->ht < u->ht)
		swap(v, u);
	int diff = v->ht - u->ht;
	Loop (i,0,lg)
		if ((diff >> i) & 1)
			v = v->anc[i];
	if (v == u)
		return v;
	LoopR (i,0,lg) {
		if (v->anc[i] != u->anc[i]) {
			v = v->anc[i];
			u = u->anc[i];
		}
	}
	return v->anc[0];
}

gnode gn[N];
snode col_snode[N];
int n, k;

void init_col_snode()
{
	Loop (i,0,k) {
		col_snode[i].weight = 1;
		all_snodes.push_back(&col_snode[i]);
	}
}

snode *make_seg(snode **ptr, int l, int r)
{
	if (r - l == 1)
		return ptr[l];
	snode *sn = new_snode();
	snode::add_edge(sn, make_seg(ptr, l, (l + r)/2));
	snode::add_edge(sn, make_seg(ptr, (l + r)/2, r));
	return sn;
}

snode *make_seg(gnode *u, gnode *d)
{
	vector<snode *> vec(d->ht - u->ht + 1);
	gnode *v = d;
	Loop (i,0,vec.size()) {
		vec.end()[-i-1] = &col_snode[v->col];
		v = v->par;
	}
	return make_seg(vec.data() - u->ht, u->ht, d->ht + 1);
}

template<typename Fn>
void seg_apply(snode *v, Fn fn, int l, int r, int b, int e)
{
	if (l <= b && e <= r) {
		fn(v);
		return;
	}
	if (r <= b || e <= l)
		return;
	seg_apply(v->adj[0], fn, l, r, b, (b+e)/2);
	seg_apply(v->adj[1], fn, l, r, (b+e)/2, e);
}

template<typename Fn>
void seg_apply(gnode *v, Fn fn, int l, int r)
{
	//cerr << v - graph << ' ' << l << ' ' << r << '\n';
	seg_apply(v->sroot, fn, l, r, v->ht, v->hleaf->ht + 1);
}

void dfsg2(gnode *v, gnode *p, gnode *hroot)
{
	for (gnode *u : v->adj) {
		if (u == p)
			continue;
		dfsg2(u, v, u == v->hchild? hroot: u);
	}
	v->hleaf = v->hchild? v->hchild->hleaf: v;
	v->hroot = hroot;
	if (v == hroot)
		v->sroot = make_seg(v, v->hleaf);
}

template<typename Fn>
void path_apply(gnode *u, gnode *d, Fn fn)
{
	while (d->hroot->ht > u->ht) {
		gnode *h = d->hroot;
		seg_apply(h, fn, h->ht, d->ht + 1);
		d = h->par;
	}
	gnode *h = d->hroot;
	assert(h == u->hroot);
	seg_apply(h, fn, u->ht, d->ht + 1);
}

void path_add_col_to(gnode *u, gnode *d, snode *col_node)
{
	//cerr << col_node - col_snode << " => " << u - graph << " --- " << d - graph << '\n';
	path_apply(u, d, [=](snode *sn) {
		//cerr << col_node - col_snode << " -> " << sn - col_snode << '\n';
		snode::add_edge(col_node, sn);
	});
	// while (d && d->ht >= u->ht) {
	// 	snode::add_edge(col_node, &col_snode[d->col]);
	// 	//cerr << col_node - col_snode << " -> " << d->col << '\n';
	// 	d = d->par;
	// }
}

void scc_dfs1(snode *v, vector<snode *> &vec)
{
	v->vis = 1;
	for (snode *u : v->adj) {
		if (!u->vis)
			scc_dfs1(u, vec);
	}
	vec.push_back(v);
}

int scc_dfs2(snode *v, int viscol)
{
	v->vis = viscol;
	int ans = v->weight;
	for (snode *u : v->adjt) {
		if (u->vis == -1)
			ans += scc_dfs2(u, viscol);
	}
	return ans;
}

int scc_solve()
{
	vector<snode *> vec;
	for (snode *sn : all_snodes)
		sn->vis = 0;
	for (snode *sn : all_snodes) {
		if (!sn->vis)
			scc_dfs1(sn, vec);
	}
	reverse(vec.begin(), vec.end());
	for (snode *sn : all_snodes)
		sn->vis = -1;
	vector<int> scc_weight;
	for (snode *sn : vec) {
		if (sn->vis != -1)
			continue;
		int x = scc_dfs2(sn, scc_weight.size());
		scc_weight.push_back(x);
	}
	vector<bool> scc_ok(scc_weight.size(), true);
	//Loop (i,0,k)
	//	cerr << i << ": " << col_snode[i].vis << '\n';
	for (snode *v : all_snodes) for (snode *u : v->adj) {
		if (v->vis != u->vis)
			scc_ok[v->vis] = false;
	}
	int ans = INT_MAX;
	Loop (i,0,scc_weight.size()) {
		if (!scc_ok[i])
			continue;
		assert(scc_weight[i]);
		ans = min(ans, scc_weight[i]);
	}
	return ans;
}

vector<gnode *> gnodes_of_col[N];

void make_virtuals()
{
	auto cmp = [](gnode *v, gnode *u) { return v->st < u->st; };
	Loop (col,0,k) {
		vector<gnode *> vec = gnodes_of_col[col];
		sort(vec.begin(), vec.end(), cmp);
		if (vec.empty())
			continue;

		gnode *l = lca(vec.front(), vec.back());

		for (gnode *v : vec)
			path_add_col_to(l, v, &col_snode[col]);
	}
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> k;
	Loop (i,0,n-1) {
		int v, u;
		cin >> v >> u;
		--v; --u;
		graph[v].adj.push_back(&graph[u]);
		graph[u].adj.push_back(&graph[v]);
	}
	Loop (i,0,n) {
		gnode *v = &graph[i];
		cin >> v->col;
		v->col--;
		gnodes_of_col[v->col].push_back(v);
	}
	init_col_snode();
	int dummy = 0;
	dfsg1(&graph[0], nullptr, dummy, 0);
	dfsg2(&graph[0], nullptr, &graph[0]);
	make_virtuals();
	int ans = scc_solve();
	cout << ans-1 << '\n';
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 171092 KB Output is correct
2 Correct 59 ms 171240 KB Output is correct
3 Correct 54 ms 171088 KB Output is correct
4 Correct 52 ms 171092 KB Output is correct
5 Correct 52 ms 171296 KB Output is correct
6 Correct 54 ms 171088 KB Output is correct
7 Correct 53 ms 171196 KB Output is correct
8 Correct 55 ms 171292 KB Output is correct
9 Correct 52 ms 171192 KB Output is correct
10 Correct 52 ms 171092 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 171092 KB Output is correct
2 Correct 59 ms 171240 KB Output is correct
3 Correct 54 ms 171088 KB Output is correct
4 Correct 52 ms 171092 KB Output is correct
5 Correct 52 ms 171296 KB Output is correct
6 Correct 54 ms 171088 KB Output is correct
7 Correct 53 ms 171196 KB Output is correct
8 Correct 55 ms 171292 KB Output is correct
9 Correct 52 ms 171192 KB Output is correct
10 Correct 52 ms 171092 KB Output is correct
11 Correct 59 ms 171724 KB Output is correct
12 Correct 58 ms 171600 KB Output is correct
13 Correct 50 ms 171772 KB Output is correct
14 Correct 55 ms 171788 KB Output is correct
15 Correct 52 ms 171604 KB Output is correct
16 Correct 53 ms 171604 KB Output is correct
17 Correct 52 ms 171860 KB Output is correct
18 Correct 54 ms 171912 KB Output is correct
19 Correct 56 ms 171856 KB Output is correct
20 Correct 55 ms 171904 KB Output is correct
21 Correct 60 ms 171916 KB Output is correct
22 Correct 55 ms 171856 KB Output is correct
23 Correct 64 ms 171864 KB Output is correct
24 Correct 58 ms 171604 KB Output is correct
25 Correct 56 ms 171928 KB Output is correct
26 Correct 54 ms 171856 KB Output is correct
27 Correct 51 ms 171852 KB Output is correct
28 Correct 56 ms 171884 KB Output is correct
29 Correct 54 ms 171856 KB Output is correct
30 Correct 54 ms 171828 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 690 ms 263288 KB Output is correct
2 Correct 327 ms 262336 KB Output is correct
3 Correct 675 ms 263148 KB Output is correct
4 Correct 320 ms 262560 KB Output is correct
5 Correct 656 ms 260620 KB Output is correct
6 Correct 329 ms 262980 KB Output is correct
7 Correct 625 ms 260176 KB Output is correct
8 Correct 297 ms 259308 KB Output is correct
9 Correct 439 ms 242084 KB Output is correct
10 Correct 431 ms 239400 KB Output is correct
11 Correct 441 ms 241952 KB Output is correct
12 Correct 458 ms 243752 KB Output is correct
13 Correct 437 ms 239108 KB Output is correct
14 Correct 555 ms 244020 KB Output is correct
15 Correct 448 ms 245004 KB Output is correct
16 Correct 459 ms 240892 KB Output is correct
17 Correct 454 ms 240968 KB Output is correct
18 Correct 449 ms 240296 KB Output is correct
19 Correct 469 ms 243664 KB Output is correct
20 Correct 459 ms 241552 KB Output is correct
21 Correct 54 ms 171312 KB Output is correct

Subtask #4
59.0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 171092 KB Output is correct
2 Correct 59 ms 171240 KB Output is correct
3 Correct 54 ms 171088 KB Output is correct
4 Correct 52 ms 171092 KB Output is correct
5 Correct 52 ms 171296 KB Output is correct
6 Correct 54 ms 171088 KB Output is correct
7 Correct 53 ms 171196 KB Output is correct
8 Correct 55 ms 171292 KB Output is correct
9 Correct 52 ms 171192 KB Output is correct
10 Correct 52 ms 171092 KB Output is correct
11 Correct 59 ms 171724 KB Output is correct
12 Correct 58 ms 171600 KB Output is correct
13 Correct 50 ms 171772 KB Output is correct
14 Correct 55 ms 171788 KB Output is correct
15 Correct 52 ms 171604 KB Output is correct
16 Correct 53 ms 171604 KB Output is correct
17 Correct 52 ms 171860 KB Output is correct
18 Correct 54 ms 171912 KB Output is correct
19 Correct 56 ms 171856 KB Output is correct
20 Correct 55 ms 171904 KB Output is correct
21 Correct 60 ms 171916 KB Output is correct
22 Correct 55 ms 171856 KB Output is correct
23 Correct 64 ms 171864 KB Output is correct
24 Correct 58 ms 171604 KB Output is correct
25 Correct 56 ms 171928 KB Output is correct
26 Correct 54 ms 171856 KB Output is correct
27 Correct 51 ms 171852 KB Output is correct
28 Correct 56 ms 171884 KB Output is correct
29 Correct 54 ms 171856 KB Output is correct
30 Correct 54 ms 171828 KB Output is correct
31 Correct 690 ms 263288 KB Output is correct
32 Correct 327 ms 262336 KB Output is correct
33 Correct 675 ms 263148 KB Output is correct
34 Correct 320 ms 262560 KB Output is correct
35 Correct 656 ms 260620 KB Output is correct
36 Correct 329 ms 262980 KB Output is correct
37 Correct 625 ms 260176 KB Output is correct
38 Correct 297 ms 259308 KB Output is correct
39 Correct 439 ms 242084 KB Output is correct
40 Correct 431 ms 239400 KB Output is correct
41 Correct 441 ms 241952 KB Output is correct
42 Correct 458 ms 243752 KB Output is correct
43 Correct 437 ms 239108 KB Output is correct
44 Correct 555 ms 244020 KB Output is correct
45 Correct 448 ms 245004 KB Output is correct
46 Correct 459 ms 240892 KB Output is correct
47 Correct 454 ms 240968 KB Output is correct
48 Correct 449 ms 240296 KB Output is correct
49 Correct 469 ms 243664 KB Output is correct
50 Correct 459 ms 241552 KB Output is correct
51 Correct 54 ms 171312 KB Output is correct
52 Correct 442 ms 227008 KB Output is correct
53 Correct 462 ms 228292 KB Output is correct
54 Correct 449 ms 227912 KB Output is correct
55 Correct 464 ms 228284 KB Output is correct
56 Correct 464 ms 226268 KB Output is correct
57 Correct 446 ms 227264 KB Output is correct
58 Correct 463 ms 229268 KB Output is correct
59 Correct 469 ms 227312 KB Output is correct
60 Correct 537 ms 234680 KB Output is correct
61 Correct 576 ms 239752 KB Output is correct
62 Correct 321 ms 262476 KB Output is correct
63 Correct 342 ms 262304 KB Output is correct
64 Correct 300 ms 261292 KB Output is correct
65 Correct 321 ms 262304 KB Output is correct
66 Correct 370 ms 272780 KB Output is correct
67 Correct 330 ms 232780 KB Output is correct
68 Correct 359 ms 267912 KB Output is correct
69 Correct 353 ms 261548 KB Output is correct
70 Correct 357 ms 260748 KB Output is correct
71 Correct 374 ms 268996 KB Output is correct
72 Correct 370 ms 266128 KB Output is correct
73 Correct 331 ms 240116 KB Output is correct
74 Correct 354 ms 260956 KB Output is correct
75 Correct 354 ms 269452 KB Output is correct
76 Correct 398 ms 212748 KB Output is correct
77 Correct 423 ms 211132 KB Output is correct
78 Correct 462 ms 240104 KB Output is correct
79 Correct 449 ms 238732 KB Output is correct
80 Correct 431 ms 243268 KB Output is correct
81 Correct 441 ms 241288 KB Output is correct
82 Correct 482 ms 241304 KB Output is correct
83 Correct 446 ms 237908 KB Output is correct
84 Correct 453 ms 241240 KB Output is correct
85 Correct 462 ms 242592 KB Output is correct
86 Correct 443 ms 242524 KB Output is correct
87 Correct 464 ms 241072 KB Output is correct
88 Correct 429 ms 238464 KB Output is correct
89 Correct 471 ms 236888 KB Output is correct
90 Correct 428 ms 235288 KB Output is correct
91 Correct 419 ms 235036 KB Output is correct
92 Correct 403 ms 239520 KB Output is correct
93 Correct 446 ms 237612 KB Output is correct
94 Correct 437 ms 235084 KB Output is correct
95 Correct 458 ms 238200 KB Output is correct
96 Correct 451 ms 234536 KB Output is correct
97 Correct 480 ms 240428 KB Output is correct