oj.uz

답안 #1039912

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1039912 2024-07-31T12:09:34 Z ymm 수도 (JOI20_capital_city) C++17
100 / 100
 721 ms 263212 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;

		int cnt = vec.size();
		Loop (i,0,cnt-1)
			vec.push_back(lca(vec[i], vec[i + 1]));
		sort(vec.begin(), vec.end(), cmp);

		vector<gnode *> st;
		for (gnode *v : vec) {
			while (st.size() && st.back()->ft <= v->st)
				st.pop_back();
			if (st.size())
				path_add_col_to(st.back(), v, &col_snode[col]);
			st.push_back(v);
		}
	}
}

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

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 171088 KB Output is correct
2 Correct 53 ms 171088 KB Output is correct
3 Correct 50 ms 171164 KB Output is correct
4 Correct 51 ms 171088 KB Output is correct
5 Correct 53 ms 171092 KB Output is correct
6 Correct 62 ms 171092 KB Output is correct
7 Correct 50 ms 171092 KB Output is correct
8 Correct 55 ms 171092 KB Output is correct
9 Correct 52 ms 171088 KB Output is correct
10 Correct 52 ms 171092 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 171088 KB Output is correct
2 Correct 53 ms 171088 KB Output is correct
3 Correct 50 ms 171164 KB Output is correct
4 Correct 51 ms 171088 KB Output is correct
5 Correct 53 ms 171092 KB Output is correct
6 Correct 62 ms 171092 KB Output is correct
7 Correct 50 ms 171092 KB Output is correct
8 Correct 55 ms 171092 KB Output is correct
9 Correct 52 ms 171088 KB Output is correct
10 Correct 52 ms 171092 KB Output is correct
11 Correct 55 ms 171612 KB Output is correct
12 Correct 54 ms 171576 KB Output is correct
13 Correct 53 ms 171604 KB Output is correct
14 Correct 58 ms 171604 KB Output is correct
15 Correct 53 ms 171604 KB Output is correct
16 Correct 53 ms 171780 KB Output is correct
17 Correct 52 ms 171600 KB Output is correct
18 Correct 52 ms 171600 KB Output is correct
19 Correct 52 ms 171604 KB Output is correct
20 Correct 55 ms 171600 KB Output is correct
21 Correct 58 ms 171600 KB Output is correct
22 Correct 60 ms 171856 KB Output is correct
23 Correct 54 ms 171856 KB Output is correct
24 Correct 53 ms 171604 KB Output is correct
25 Correct 57 ms 171856 KB Output is correct
26 Correct 56 ms 171860 KB Output is correct
27 Correct 55 ms 171684 KB Output is correct
28 Correct 53 ms 171608 KB Output is correct
29 Correct 51 ms 171604 KB Output is correct
30 Correct 53 ms 171600 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 721 ms 263212 KB Output is correct
2 Correct 324 ms 262432 KB Output is correct
3 Correct 701 ms 263132 KB Output is correct
4 Correct 320 ms 262364 KB Output is correct
5 Correct 671 ms 258360 KB Output is correct
6 Correct 314 ms 262300 KB Output is correct
7 Correct 667 ms 256084 KB Output is correct
8 Correct 314 ms 255512 KB Output is correct
9 Correct 487 ms 226208 KB Output is correct
10 Correct 453 ms 224176 KB Output is correct
11 Correct 450 ms 226720 KB Output is correct
12 Correct 451 ms 229648 KB Output is correct
13 Correct 514 ms 225288 KB Output is correct
14 Correct 455 ms 229364 KB Output is correct
15 Correct 475 ms 231180 KB Output is correct
16 Correct 459 ms 224872 KB Output is correct
17 Correct 459 ms 226368 KB Output is correct
18 Correct 465 ms 224968 KB Output is correct
19 Correct 504 ms 230272 KB Output is correct
20 Correct 448 ms 228764 KB Output is correct
21 Correct 53 ms 171092 KB Output is correct

Subtask #4
59.0 / 59.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 171088 KB Output is correct
2 Correct 53 ms 171088 KB Output is correct
3 Correct 50 ms 171164 KB Output is correct
4 Correct 51 ms 171088 KB Output is correct
5 Correct 53 ms 171092 KB Output is correct
6 Correct 62 ms 171092 KB Output is correct
7 Correct 50 ms 171092 KB Output is correct
8 Correct 55 ms 171092 KB Output is correct
9 Correct 52 ms 171088 KB Output is correct
10 Correct 52 ms 171092 KB Output is correct
11 Correct 55 ms 171612 KB Output is correct
12 Correct 54 ms 171576 KB Output is correct
13 Correct 53 ms 171604 KB Output is correct
14 Correct 58 ms 171604 KB Output is correct
15 Correct 53 ms 171604 KB Output is correct
16 Correct 53 ms 171780 KB Output is correct
17 Correct 52 ms 171600 KB Output is correct
18 Correct 52 ms 171600 KB Output is correct
19 Correct 52 ms 171604 KB Output is correct
20 Correct 55 ms 171600 KB Output is correct
21 Correct 58 ms 171600 KB Output is correct
22 Correct 60 ms 171856 KB Output is correct
23 Correct 54 ms 171856 KB Output is correct
24 Correct 53 ms 171604 KB Output is correct
25 Correct 57 ms 171856 KB Output is correct
26 Correct 56 ms 171860 KB Output is correct
27 Correct 55 ms 171684 KB Output is correct
28 Correct 53 ms 171608 KB Output is correct
29 Correct 51 ms 171604 KB Output is correct
30 Correct 53 ms 171600 KB Output is correct
31 Correct 721 ms 263212 KB Output is correct
32 Correct 324 ms 262432 KB Output is correct
33 Correct 701 ms 263132 KB Output is correct
34 Correct 320 ms 262364 KB Output is correct
35 Correct 671 ms 258360 KB Output is correct
36 Correct 314 ms 262300 KB Output is correct
37 Correct 667 ms 256084 KB Output is correct
38 Correct 314 ms 255512 KB Output is correct
39 Correct 487 ms 226208 KB Output is correct
40 Correct 453 ms 224176 KB Output is correct
41 Correct 450 ms 226720 KB Output is correct
42 Correct 451 ms 229648 KB Output is correct
43 Correct 514 ms 225288 KB Output is correct
44 Correct 455 ms 229364 KB Output is correct
45 Correct 475 ms 231180 KB Output is correct
46 Correct 459 ms 224872 KB Output is correct
47 Correct 459 ms 226368 KB Output is correct
48 Correct 465 ms 224968 KB Output is correct
49 Correct 504 ms 230272 KB Output is correct
50 Correct 448 ms 228764 KB Output is correct
51 Correct 53 ms 171092 KB Output is correct
52 Correct 483 ms 227784 KB Output is correct
53 Correct 495 ms 227776 KB Output is correct
54 Correct 487 ms 228132 KB Output is correct
55 Correct 483 ms 228244 KB Output is correct
56 Correct 484 ms 227528 KB Output is correct
57 Correct 493 ms 227564 KB Output is correct
58 Correct 484 ms 220192 KB Output is correct
59 Correct 464 ms 219332 KB Output is correct
60 Correct 580 ms 231744 KB Output is correct
61 Correct 584 ms 235964 KB Output is correct
62 Correct 322 ms 262300 KB Output is correct
63 Correct 316 ms 262300 KB Output is correct
64 Correct 293 ms 257648 KB Output is correct
65 Correct 323 ms 262300 KB Output is correct
66 Correct 364 ms 231312 KB Output is correct
67 Correct 348 ms 222012 KB Output is correct
68 Correct 344 ms 229040 KB Output is correct
69 Correct 355 ms 228976 KB Output is correct
70 Correct 381 ms 228940 KB Output is correct
71 Correct 382 ms 229016 KB Output is correct
72 Correct 383 ms 229036 KB Output is correct
73 Correct 385 ms 230052 KB Output is correct
74 Correct 404 ms 229556 KB Output is correct
75 Correct 355 ms 230588 KB Output is correct
76 Correct 440 ms 212500 KB Output is correct
77 Correct 465 ms 211264 KB Output is correct
78 Correct 537 ms 225800 KB Output is correct
79 Correct 467 ms 224960 KB Output is correct
80 Correct 445 ms 228120 KB Output is correct
81 Correct 484 ms 226724 KB Output is correct
82 Correct 455 ms 228288 KB Output is correct
83 Correct 445 ms 224744 KB Output is correct
84 Correct 530 ms 231296 KB Output is correct
85 Correct 484 ms 227844 KB Output is correct
86 Correct 452 ms 225140 KB Output is correct
87 Correct 454 ms 225024 KB Output is correct
88 Correct 493 ms 226852 KB Output is correct
89 Correct 467 ms 220720 KB Output is correct
90 Correct 458 ms 219936 KB Output is correct
91 Correct 438 ms 221832 KB Output is correct
92 Correct 481 ms 224172 KB Output is correct
93 Correct 471 ms 221224 KB Output is correct
94 Correct 462 ms 220984 KB Output is correct
95 Correct 448 ms 221744 KB Output is correct
96 Correct 478 ms 224616 KB Output is correct
97 Correct 531 ms 224312 KB Output is correct