oj.uz

Submission #216732

# Submission time Handle Problem Language Result Execution time Memory
216732 2020-03-27T23:50:37 Z ainta Capital City (JOI20_capital_city) C++17
100 / 100
 962 ms 174600 KB 
#include<cstdio>
#include<algorithm>
#include<vector>
#define N_ 210000
#define M_ 1010000
using namespace std;
vector<int>E[N_], G[M_], P[N_], H[M_];
int n, w[N_], K, C[N_], Dep[N_], par[N_][20], PPP[N_], Num[N_], Ed[N_], ReNum[N_], cnt;
void DFS(int a, int pp) {
	par[a][0] = pp;
	C[a] = 1;
	for (int i = 0; i < 18; i++)par[a][i + 1] = par[par[a][i]][i];
	for (auto &x : E[a]) {
		if (x != pp) {
			Dep[x] = Dep[a] + 1;
			DFS(x, a);
			C[a] += C[x];
		}
	}
}
void HLD(int a, int pp, int rt) {
	Num[a] = ++cnt;
	ReNum[cnt] = a;
	G[n + cnt].push_back(w[a]);
	PPP[a] = rt;
	int Mx = -1, pv = -1;
	for (auto &x : E[a]) {
		if (x == pp)continue;
		if (Mx < C[x])Mx = C[x], pv = x;
	}
	if (pv != -1) {
		G[n+cnt + 1].push_back(n+cnt);
		HLD(pv, a, rt);
	}
	for (auto &x : E[a]) {
		if (x != pp && x != pv)HLD(x, a, x);
	}
}
int LCA(int a, int b) {
	if (Dep[a] < Dep[b])return LCA(b, a);
	int d = Dep[a] - Dep[b], i;
	for (i = 0; i < 18; i++)if ((d >> i) & 1)a = par[a][i];
	for (i = 17; i >= 0; i--)if (par[a][i] != par[b][i])a = par[a][i], b = par[b][i];
	if (a != b)a = par[a][0];
	return a;
}
void MEdge(int st, int nd, int b, int e, int s, int l) {
	if (s > l)return;
	if (s <= b && e <= l) {
		G[st].push_back(n + n + nd);
		return;
	}
	int m = (b + e) >> 1;
	if (s <= m)MEdge(st, nd * 2, b, m, s, l);
	if (l > m)MEdge(st, nd * 2 + 1, m + 1, e, s, l);
}
void Make_Edge(int st, int a, int p) {
	while (1) {
		if (Dep[PPP[a]] <= Dep[p]) {
			MEdge(st, 1, 1, n, Num[p], Num[a]);
			return;
		}
		G[st].push_back(n+Num[a]);
		a = par[PPP[a]][0];
	}
}
void Build(int nd, int b, int e) {
	if (b == e) {
		G[n + n + nd].push_back(w[ReNum[b]]);
		return;
	}
	int m = (b + e) >> 1;
	G[n + n + nd].push_back(n + n + nd * 2);
	G[n + n + nd].push_back(n + n + nd * 2 + 1);
	Build(nd * 2, b, m);
	Build(nd * 2 + 1, m + 1, e);
}
int ord[M_], SCC[M_], cc, sc, CC[M_];
bool chk[M_], vis[M_];
void DFS1(int a) {
	vis[a] = 1;
	for (auto &x : G[a]) {
		if (!vis[x])DFS1(x);
	}
	ord[++cc] = a;
}
void DFS2(int a) {
	SCC[a] = sc;
	if (a <= K)CC[sc]++;
	for (auto &x : H[a]) {
		if (!SCC[x])DFS2(x);
	}
}
int main() {
	//freopen("input.txt", "r", stdin);
	int i;
	scanf("%d%d", &n,&K);
	for (i = 1; i < n; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		E[a].push_back(b);
		E[b].push_back(a);
	}
	for (i = 1; i <= n; i++) {
		scanf("%d", &w[i]);
		P[w[i]].push_back(i);
	}
	DFS(1, 0);
	HLD(1, 0, 1);
	Build(1, 1, n);
	for (i = 1; i <= K; i++) {
		int a = P[i][0];
		for (auto &t : P[i])a = LCA(a, t);
		for (auto &t : P[i]) {
			Make_Edge(i, t, a);
		}
	}
	for (i = 1; i < M_; i++) {
		for (auto &t : G[i]) {
			H[t].push_back(i);
		}
	}
	for (i = 1; i < M_; i++) {
		if (!vis[i]) {
			DFS1(i);
		}
	}
	for (i = cc; i >= 1; i--) {
		if (!SCC[ord[i]]) {
			sc++;
			DFS2(ord[i]);
		}
	}
	for (i = 1; i < M_; i++) {
		for (auto &t : G[i]) {
			if (SCC[i] != SCC[t]) {
				chk[SCC[i]] = 1;
			}
		}
	}
	int res = 1e9;
	for (i = 1; i <= sc; i++) {
		if (!chk[i] && CC[i])res = min(res, CC[i]);
	}
	printf("%d\n",res - 1);
}

Compilation message

capital_city.cpp: In function 'int main()':
capital_city.cpp:97:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n,&K);
  ~~~~~^~~~~~~~~~~~~~~
capital_city.cpp:100:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~
capital_city.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &w[i]);
   ~~~~~^~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 66660 KB Output is correct
2 Correct 64 ms 66536 KB Output is correct
3 Correct 72 ms 66552 KB Output is correct
4 Correct 64 ms 66552 KB Output is correct
5 Correct 63 ms 66552 KB Output is correct
6 Correct 69 ms 66552 KB Output is correct
7 Correct 64 ms 66552 KB Output is correct
8 Correct 64 ms 66552 KB Output is correct
9 Correct 64 ms 66552 KB Output is correct
10 Correct 62 ms 66552 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 66660 KB Output is correct
2 Correct 64 ms 66536 KB Output is correct
3 Correct 72 ms 66552 KB Output is correct
4 Correct 64 ms 66552 KB Output is correct
5 Correct 63 ms 66552 KB Output is correct
6 Correct 69 ms 66552 KB Output is correct
7 Correct 64 ms 66552 KB Output is correct
8 Correct 64 ms 66552 KB Output is correct
9 Correct 64 ms 66552 KB Output is correct
10 Correct 62 ms 66552 KB Output is correct
11 Correct 66 ms 67320 KB Output is correct
12 Correct 65 ms 67320 KB Output is correct
13 Correct 66 ms 67320 KB Output is correct
14 Correct 72 ms 67320 KB Output is correct
15 Correct 68 ms 67424 KB Output is correct
16 Correct 68 ms 67452 KB Output is correct
17 Correct 67 ms 67448 KB Output is correct
18 Correct 66 ms 67572 KB Output is correct
19 Correct 66 ms 67452 KB Output is correct
20 Correct 67 ms 67448 KB Output is correct
21 Correct 69 ms 67448 KB Output is correct
22 Correct 67 ms 67576 KB Output is correct
23 Correct 67 ms 67448 KB Output is correct
24 Correct 72 ms 67320 KB Output is correct
25 Correct 67 ms 67448 KB Output is correct
26 Correct 67 ms 67448 KB Output is correct
27 Correct 67 ms 67448 KB Output is correct
28 Correct 67 ms 67448 KB Output is correct
29 Correct 67 ms 67352 KB Output is correct
30 Correct 75 ms 67448 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 962 ms 173684 KB Output is correct
2 Correct 564 ms 174512 KB Output is correct
3 Correct 936 ms 172804 KB Output is correct
4 Correct 585 ms 174576 KB Output is correct
5 Correct 917 ms 166068 KB Output is correct
6 Correct 571 ms 174580 KB Output is correct
7 Correct 876 ms 166700 KB Output is correct
8 Correct 529 ms 172396 KB Output is correct
9 Correct 753 ms 159544 KB Output is correct
10 Correct 745 ms 154760 KB Output is correct
11 Correct 760 ms 159340 KB Output is correct
12 Correct 798 ms 164332 KB Output is correct
13 Correct 764 ms 153076 KB Output is correct
14 Correct 780 ms 164588 KB Output is correct
15 Correct 808 ms 164420 KB Output is correct
16 Correct 757 ms 156812 KB Output is correct
17 Correct 776 ms 158628 KB Output is correct
18 Correct 764 ms 156560 KB Output is correct
19 Correct 819 ms 163100 KB Output is correct
20 Correct 785 ms 165476 KB Output is correct
21 Correct 64 ms 66560 KB Output is correct

Subtask #4
59.0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 66660 KB Output is correct
2 Correct 64 ms 66536 KB Output is correct
3 Correct 72 ms 66552 KB Output is correct
4 Correct 64 ms 66552 KB Output is correct
5 Correct 63 ms 66552 KB Output is correct
6 Correct 69 ms 66552 KB Output is correct
7 Correct 64 ms 66552 KB Output is correct
8 Correct 64 ms 66552 KB Output is correct
9 Correct 64 ms 66552 KB Output is correct
10 Correct 62 ms 66552 KB Output is correct
11 Correct 66 ms 67320 KB Output is correct
12 Correct 65 ms 67320 KB Output is correct
13 Correct 66 ms 67320 KB Output is correct
14 Correct 72 ms 67320 KB Output is correct
15 Correct 68 ms 67424 KB Output is correct
16 Correct 68 ms 67452 KB Output is correct
17 Correct 67 ms 67448 KB Output is correct
18 Correct 66 ms 67572 KB Output is correct
19 Correct 66 ms 67452 KB Output is correct
20 Correct 67 ms 67448 KB Output is correct
21 Correct 69 ms 67448 KB Output is correct
22 Correct 67 ms 67576 KB Output is correct
23 Correct 67 ms 67448 KB Output is correct
24 Correct 72 ms 67320 KB Output is correct
25 Correct 67 ms 67448 KB Output is correct
26 Correct 67 ms 67448 KB Output is correct
27 Correct 67 ms 67448 KB Output is correct
28 Correct 67 ms 67448 KB Output is correct
29 Correct 67 ms 67352 KB Output is correct
30 Correct 75 ms 67448 KB Output is correct
31 Correct 962 ms 173684 KB Output is correct
32 Correct 564 ms 174512 KB Output is correct
33 Correct 936 ms 172804 KB Output is correct
34 Correct 585 ms 174576 KB Output is correct
35 Correct 917 ms 166068 KB Output is correct
36 Correct 571 ms 174580 KB Output is correct
37 Correct 876 ms 166700 KB Output is correct
38 Correct 529 ms 172396 KB Output is correct
39 Correct 753 ms 159544 KB Output is correct
40 Correct 745 ms 154760 KB Output is correct
41 Correct 760 ms 159340 KB Output is correct
42 Correct 798 ms 164332 KB Output is correct
43 Correct 764 ms 153076 KB Output is correct
44 Correct 780 ms 164588 KB Output is correct
45 Correct 808 ms 164420 KB Output is correct
46 Correct 757 ms 156812 KB Output is correct
47 Correct 776 ms 158628 KB Output is correct
48 Correct 764 ms 156560 KB Output is correct
49 Correct 819 ms 163100 KB Output is correct
50 Correct 785 ms 165476 KB Output is correct
51 Correct 64 ms 66560 KB Output is correct
52 Correct 753 ms 147272 KB Output is correct
53 Correct 744 ms 148256 KB Output is correct
54 Correct 732 ms 148200 KB Output is correct
55 Correct 749 ms 147808 KB Output is correct
56 Correct 727 ms 147808 KB Output is correct
57 Correct 723 ms 148076 KB Output is correct
58 Correct 748 ms 148472 KB Output is correct
59 Correct 794 ms 149344 KB Output is correct
60 Correct 894 ms 151664 KB Output is correct
61 Correct 846 ms 152724 KB Output is correct
62 Correct 572 ms 174600 KB Output is correct
63 Correct 604 ms 174576 KB Output is correct
64 Correct 585 ms 173412 KB Output is correct
65 Correct 570 ms 174380 KB Output is correct
66 Correct 703 ms 169924 KB Output is correct
67 Correct 607 ms 156252 KB Output is correct
68 Correct 720 ms 169924 KB Output is correct
69 Correct 737 ms 169820 KB Output is correct
70 Correct 772 ms 170048 KB Output is correct
71 Correct 768 ms 169808 KB Output is correct
72 Correct 774 ms 169832 KB Output is correct
73 Correct 680 ms 154852 KB Output is correct
74 Correct 744 ms 169796 KB Output is correct
75 Correct 751 ms 170028 KB Output is correct
76 Correct 777 ms 147808 KB Output is correct
77 Correct 793 ms 145564 KB Output is correct
78 Correct 857 ms 156608 KB Output is correct
79 Correct 894 ms 155324 KB Output is correct
80 Correct 851 ms 164636 KB Output is correct
81 Correct 878 ms 158540 KB Output is correct
82 Correct 886 ms 158868 KB Output is correct
83 Correct 876 ms 152736 KB Output is correct
84 Correct 897 ms 161976 KB Output is correct
85 Correct 856 ms 160232 KB Output is correct
86 Correct 941 ms 156448 KB Output is correct
87 Correct 899 ms 156564 KB Output is correct
88 Correct 873 ms 160304 KB Output is correct
89 Correct 845 ms 153568 KB Output is correct
90 Correct 833 ms 153620 KB Output is correct
91 Correct 879 ms 157672 KB Output is correct
92 Correct 903 ms 155932 KB Output is correct
93 Correct 878 ms 155764 KB Output is correct
94 Correct 857 ms 154320 KB Output is correct
95 Correct 863 ms 155240 KB Output is correct
96 Correct 851 ms 153368 KB Output is correct
97 Correct 860 ms 160504 KB Output is correct