oj.uz

Submission #609708

# Submission time Handle Problem Language Result Execution time Memory
609708 2022-07-27T19:34:37 Z penguinhacker Capital City (JOI20_capital_city) C++17
100 / 100
 1032 ms 163708 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ar array
 
const int mxN=2e5, MX=1e6;
int n, k, c[mxN], n2;
int d[mxN], s[mxN], p[mxN], hd[mxN], tin[mxN], tin2[mxN];
vector<int> oc[mxN], adj1[mxN], nodes;
vector<int> adj2[MX], adj3[MX], st;
int who[MX], cnt[MX];
bool vis[MX], out[MX];
 
void dfs1(int u=0) {
	s[u]=1;
	for (int& v : adj1[u]) {
		adj1[v].erase(find(adj1[v].begin(), adj1[v].end(), u));
		d[v]=d[u]+1, p[v]=u;
		dfs1(v);
		s[u]+=s[v];
		if (s[v]>s[adj1[u][0]])
			swap(v, adj1[u][0]);
	}
}

void dfs2(int u=0, int h=0) {
	static int timer=0;
	hd[u]=h, tin[u]=timer++, tin2[tin[u]]=u;
	if (adj1[u].empty())
		return;
	dfs2(adj1[u][0], h);
	for (int i=1; i<adj1[u].size(); ++i)
		dfs2(adj1[u][i], adj1[u][i]);
}

int lca(int u, int v) {
	for (; hd[u]!=hd[v]; v=p[hd[v]])
		if (d[hd[u]]>d[hd[v]])
			swap(u, v);
	return d[u]<d[v]?u:v;
}

void ae(int u, int v) {
	adj2[u].push_back(v);
	adj3[v].push_back(u);
}

void bld(int u=1, int l=0, int r=n-1) {
	if (l==r) {
		ae(u+k, c[tin2[l]]);
		n2=max(n2, u+k+1);
		return;
	}
	int mid=(l+r)/2;
	ae(u+k, 2*u+k);
	ae(u+k, 2*u+1+k);
	bld(2*u, l, mid);
	bld(2*u+1, mid+1, r);
}

void qry(int ql, int qr, int u=1, int l=0, int r=n-1) {
	if (l>qr||r<ql)
		return;
	if (ql<=l&&r<=qr) {
		nodes.push_back(u+k);
		return;
	}
	int mid=(l+r)/2;
	qry(ql, qr, 2*u, l, mid);
	qry(ql, qr, 2*u+1, mid+1, r);
}

vector<int> gt(int u, int v) {
	assert(hd[u]==hd[v]&&tin[u]<=tin[v]);
	nodes.clear();
	qry(tin[u], tin[v]);
	return nodes;
}

void dfs3(int u) {
	vis[u]=1;
	for (int v : adj2[u])
		if (!vis[v])
			dfs3(v);
	st.push_back(u);
}

void dfs4(int u, int rt) {
	vis[u]=0, who[u]=rt;
	cnt[rt]+=u<k;
	for (int v : adj3[u])
		if (vis[v])
			dfs4(v, rt);
}
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> k;
	for (int i=1; i<n; ++i) {
		int u, v;
		cin >> u >> v, --u, --v;
		adj1[u].push_back(v);
		adj1[v].push_back(u);
	}
	for (int i=0; i<n; ++i) {
		cin >> c[i], --c[i];
		oc[c[i]].push_back(i);
	}
	dfs1();
	dfs2();
	bld();
	for (int i=0; i<n; ++i) {
		ae(i+n2, c[i]);
		if (i!=hd[i])
			ae(i+n2, p[i]+n2);
	}
	for (int i=0; i<k; ++i) {
		int l=oc[i][0];
		for (int j=1; j<oc[i].size(); ++j)
			l=lca(l, oc[i][j]);
		for (int u : oc[i]) {
			for (; hd[u]!=hd[l]; u=p[hd[u]])
				ae(i, n2+u);
			for (int j : gt(l, u))
				ae(i, j);
		}
	}
	n2+=n;
	for (int i=0; i<n2; ++i)
		if (!vis[i])
			dfs3(i);
	reverse(st.begin(), st.end());
	for (int i : st)
		if (vis[i])
			dfs4(i, i);
	for (int i : st)
		for (int j : adj2[i])
			if (who[i]!=who[j])
				out[who[i]]=1;
	int ans=69696969;
	for (int i=0; i<k; ++i)
		if (!out[who[i]])
			ans=min(ans, cnt[who[i]]-1);
	cout << ans;
	return 0;
}

Compilation message

capital_city.cpp: In function 'void dfs2(int, int)':
capital_city.cpp:33:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for (int i=1; i<adj1[u].size(); ++i)
      |                ~^~~~~~~~~~~~~~~
capital_city.cpp: In function 'int main()':
capital_city.cpp:121:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |   for (int j=1; j<oc[i].size(); ++j)
      |                 ~^~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 56644 KB Output is correct
2 Correct 26 ms 56672 KB Output is correct
3 Correct 27 ms 56648 KB Output is correct
4 Correct 35 ms 56640 KB Output is correct
5 Correct 28 ms 56664 KB Output is correct
6 Correct 27 ms 56668 KB Output is correct
7 Correct 27 ms 56748 KB Output is correct
8 Correct 25 ms 56696 KB Output is correct
9 Correct 26 ms 56704 KB Output is correct
10 Correct 27 ms 56676 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 56644 KB Output is correct
2 Correct 26 ms 56672 KB Output is correct
3 Correct 27 ms 56648 KB Output is correct
4 Correct 35 ms 56640 KB Output is correct
5 Correct 28 ms 56664 KB Output is correct
6 Correct 27 ms 56668 KB Output is correct
7 Correct 27 ms 56748 KB Output is correct
8 Correct 25 ms 56696 KB Output is correct
9 Correct 26 ms 56704 KB Output is correct
10 Correct 27 ms 56676 KB Output is correct
11 Correct 33 ms 57512 KB Output is correct
12 Correct 29 ms 57508 KB Output is correct
13 Correct 29 ms 57412 KB Output is correct
14 Correct 30 ms 57452 KB Output is correct
15 Correct 29 ms 57516 KB Output is correct
16 Correct 31 ms 57420 KB Output is correct
17 Correct 32 ms 57532 KB Output is correct
18 Correct 36 ms 57668 KB Output is correct
19 Correct 31 ms 57572 KB Output is correct
20 Correct 29 ms 57616 KB Output is correct
21 Correct 32 ms 57544 KB Output is correct
22 Correct 30 ms 57736 KB Output is correct
23 Correct 31 ms 57612 KB Output is correct
24 Correct 31 ms 57428 KB Output is correct
25 Correct 36 ms 57580 KB Output is correct
26 Correct 31 ms 57620 KB Output is correct
27 Correct 31 ms 57556 KB Output is correct
28 Correct 36 ms 57548 KB Output is correct
29 Correct 32 ms 57556 KB Output is correct
30 Correct 33 ms 57540 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1014 ms 159496 KB Output is correct
2 Correct 531 ms 159996 KB Output is correct
3 Correct 1032 ms 158752 KB Output is correct
4 Correct 489 ms 160036 KB Output is correct
5 Correct 931 ms 151908 KB Output is correct
6 Correct 485 ms 160100 KB Output is correct
7 Correct 929 ms 152492 KB Output is correct
8 Correct 458 ms 157380 KB Output is correct
9 Correct 721 ms 143876 KB Output is correct
10 Correct 724 ms 140352 KB Output is correct
11 Correct 759 ms 143344 KB Output is correct
12 Correct 740 ms 149292 KB Output is correct
13 Correct 708 ms 138064 KB Output is correct
14 Correct 769 ms 149380 KB Output is correct
15 Correct 726 ms 148496 KB Output is correct
16 Correct 761 ms 142880 KB Output is correct
17 Correct 758 ms 144340 KB Output is correct
18 Correct 739 ms 141052 KB Output is correct
19 Correct 791 ms 147388 KB Output is correct
20 Correct 763 ms 151544 KB Output is correct
21 Correct 28 ms 56720 KB Output is correct

Subtask #4
59.0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 56644 KB Output is correct
2 Correct 26 ms 56672 KB Output is correct
3 Correct 27 ms 56648 KB Output is correct
4 Correct 35 ms 56640 KB Output is correct
5 Correct 28 ms 56664 KB Output is correct
6 Correct 27 ms 56668 KB Output is correct
7 Correct 27 ms 56748 KB Output is correct
8 Correct 25 ms 56696 KB Output is correct
9 Correct 26 ms 56704 KB Output is correct
10 Correct 27 ms 56676 KB Output is correct
11 Correct 33 ms 57512 KB Output is correct
12 Correct 29 ms 57508 KB Output is correct
13 Correct 29 ms 57412 KB Output is correct
14 Correct 30 ms 57452 KB Output is correct
15 Correct 29 ms 57516 KB Output is correct
16 Correct 31 ms 57420 KB Output is correct
17 Correct 32 ms 57532 KB Output is correct
18 Correct 36 ms 57668 KB Output is correct
19 Correct 31 ms 57572 KB Output is correct
20 Correct 29 ms 57616 KB Output is correct
21 Correct 32 ms 57544 KB Output is correct
22 Correct 30 ms 57736 KB Output is correct
23 Correct 31 ms 57612 KB Output is correct
24 Correct 31 ms 57428 KB Output is correct
25 Correct 36 ms 57580 KB Output is correct
26 Correct 31 ms 57620 KB Output is correct
27 Correct 31 ms 57556 KB Output is correct
28 Correct 36 ms 57548 KB Output is correct
29 Correct 32 ms 57556 KB Output is correct
30 Correct 33 ms 57540 KB Output is correct
31 Correct 1014 ms 159496 KB Output is correct
32 Correct 531 ms 159996 KB Output is correct
33 Correct 1032 ms 158752 KB Output is correct
34 Correct 489 ms 160036 KB Output is correct
35 Correct 931 ms 151908 KB Output is correct
36 Correct 485 ms 160100 KB Output is correct
37 Correct 929 ms 152492 KB Output is correct
38 Correct 458 ms 157380 KB Output is correct
39 Correct 721 ms 143876 KB Output is correct
40 Correct 724 ms 140352 KB Output is correct
41 Correct 759 ms 143344 KB Output is correct
42 Correct 740 ms 149292 KB Output is correct
43 Correct 708 ms 138064 KB Output is correct
44 Correct 769 ms 149380 KB Output is correct
45 Correct 726 ms 148496 KB Output is correct
46 Correct 761 ms 142880 KB Output is correct
47 Correct 758 ms 144340 KB Output is correct
48 Correct 739 ms 141052 KB Output is correct
49 Correct 791 ms 147388 KB Output is correct
50 Correct 763 ms 151544 KB Output is correct
51 Correct 28 ms 56720 KB Output is correct
52 Correct 656 ms 132784 KB Output is correct
53 Correct 648 ms 133732 KB Output is correct
54 Correct 700 ms 133688 KB Output is correct
55 Correct 643 ms 133320 KB Output is correct
56 Correct 619 ms 133460 KB Output is correct
57 Correct 688 ms 133816 KB Output is correct
58 Correct 752 ms 133236 KB Output is correct
59 Correct 731 ms 134524 KB Output is correct
60 Correct 753 ms 140756 KB Output is correct
61 Correct 807 ms 142132 KB Output is correct
62 Correct 483 ms 163708 KB Output is correct
63 Correct 492 ms 163668 KB Output is correct
64 Correct 480 ms 162440 KB Output is correct
65 Correct 530 ms 163536 KB Output is correct
66 Correct 619 ms 161988 KB Output is correct
67 Correct 676 ms 144156 KB Output is correct
68 Correct 663 ms 161808 KB Output is correct
69 Correct 681 ms 161688 KB Output is correct
70 Correct 722 ms 161604 KB Output is correct
71 Correct 646 ms 161884 KB Output is correct
72 Correct 624 ms 161744 KB Output is correct
73 Correct 664 ms 142744 KB Output is correct
74 Correct 720 ms 161812 KB Output is correct
75 Correct 772 ms 162000 KB Output is correct
76 Correct 756 ms 136852 KB Output is correct
77 Correct 664 ms 134636 KB Output is correct
78 Correct 805 ms 145300 KB Output is correct
79 Correct 803 ms 143484 KB Output is correct
80 Correct 731 ms 152248 KB Output is correct
81 Correct 740 ms 146676 KB Output is correct
82 Correct 748 ms 147192 KB Output is correct
83 Correct 746 ms 141012 KB Output is correct
84 Correct 741 ms 149964 KB Output is correct
85 Correct 732 ms 148132 KB Output is correct
86 Correct 774 ms 145444 KB Output is correct
87 Correct 769 ms 145064 KB Output is correct
88 Correct 736 ms 148636 KB Output is correct
89 Correct 735 ms 142588 KB Output is correct
90 Correct 723 ms 144316 KB Output is correct
91 Correct 757 ms 145680 KB Output is correct
92 Correct 722 ms 144104 KB Output is correct
93 Correct 703 ms 144300 KB Output is correct
94 Correct 771 ms 142784 KB Output is correct
95 Correct 802 ms 143668 KB Output is correct
96 Correct 728 ms 141796 KB Output is correct
97 Correct 733 ms 148844 KB Output is correct