oj.uz

Submission #518925

# Submission time Handle Problem Language Result Execution time Memory
518925 2022-01-25T07:32:17 Z AmShZ Unique Cities (JOI19_ho_t5) C++11
100 / 100
 1926 ms 199748 KB 
//khodaya khodet komak kon
# include <bits/stdc++.h>

using namespace std;

typedef long long                                        ll;
typedef long double                                      ld;
typedef pair <int, int>                                  pii;
typedef pair <pii, int>                                  ppi;
typedef pair <int, pii>                                  pip;
typedef pair <pii, pii>                                  ppp;
typedef pair <ll, ll>                                    pll;

# define A                                               first
# define B                                               second
# define endl                                            '\n'
# define sep                                             ' '
# define all(x)                                          x.begin(), x.end()
# define kill(x)                                         return cout << x << endl, 0
# define SZ(x)                                           int(x.size())
# define lc                                              id << 1
# define rc                                              id << 1 | 1
# define fast_io                                         ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);

ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}

const int xn = 2e5 + 10;
const int xm = 10 + 10;
const int sq = 320;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const ld eps = 1e-15;
const int mod = 998244353;
const int base = 257;

int n, m, c[xn], dmx[2][xn], par[xm][xn * 3], col[xn * 3];
int dist[xm][xn * 3], P[xn], cnt[xn], s, ans[xn];
vector <int> adj[xn], g[xn * 3];
vector <pii> G[xn * 3];

void DFS1(int v, int p = - 1){
	for (int u : adj[v])
		if (u != p)
			DFS1(u, v), dmx[0][v] = max(dmx[0][v], dmx[0][u] + 1);
}
void DFS2(int v, int p = - 1){
	vector <int> vec;
	vec.push_back(dmx[1][v] + 1);
	for (int u : adj[v])
		if (u != p)
			vec.push_back(dmx[0][u] + 1);
	sort(all(vec));
	for (int u : adj[v]){
		if (u == p)
			continue;
		if (dmx[0][u] + 1 == vec.back())
			dmx[1][u] = vec[SZ(vec) - 2];
		else
			dmx[1][u] = vec.back();
		DFS2(u, v);
	}
}
void add_edge(int v, int u, int w){
	G[u].push_back({v, w});
	//cout << v << " -> " << u << " : " << w << endl;
	//par[0][v] = u;
}
void DFS3(int v, int p = - 1){
	vector <pii> vec;
	vec.push_back({0, 0});
	vec.push_back({0, 0});
	P[v] = p;
	for (int u : adj[v])
		if (u != p)
			vec.push_back({dmx[0][u] + 1, u + n});
	sort(all(vec));
	add_edge(v + n, vec.back().B, vec[SZ(vec) - 2].A);
	vec.push_back({dmx[1][v] + 1, v + n + n});
	sort(all(vec));
	add_edge(v, vec.back().B, vec[SZ(vec) - 2].A);
	for (int u : adj[v]){
		if (u == p)
			continue;
		if (u + n == vec.back().B)
			add_edge(u + n + n, vec[SZ(vec) - 2].B, vec[SZ(vec) - 3].A);
		else if (u + n == vec[SZ(vec) - 2].B)
			add_edge(u + n + n, vec[SZ(vec) - 1].B, vec[SZ(vec) - 3].A);
		else
			add_edge(u + n + n, vec[SZ(vec) - 1].B, vec[SZ(vec) - 2].A);
	}
	for (int u : adj[v])
		if (u != p)
			DFS3(u, v);
}
void DFS4(int v, int w = - 1){
	for (int i = 1; i < xm; ++ i){
		par[i][v] = par[i - 1][par[i - 1][v]];
		dist[i][v] = dist[i - 1][v] + dist[i - 1][par[i - 1][v]];
		if (!v)
			dist[i][v] = inf;
	}
	int res = v, d = 0;
	for (int i = xm - 1; 0 <= i; -- i){
		if (w < d + dist[i][res])
			continue;
		d += dist[i][res];
		res = par[i][res];
	}
	dist[0][v] = d + dist[0][res];
	par[0][v] = par[0][res];
	if (v)
		g[par[0][v]].push_back(v);
	for (int i = 1; i < xm; ++ i){
		par[i][v] = par[i - 1][par[i - 1][v]];
		dist[i][v] = dist[i - 1][v] + dist[i - 1][par[i - 1][v]];
	}
	if (!v)
		for (int i = 0; i < xm; ++ i)
			par[i][0] = 0, dist[0][0] = inf;
	for (pii u : G[v]){
		par[0][u.A] = v;
		dist[0][u.A] = 1;
		if (v == 0)
			dist[0][u.A] = inf;
		DFS4(u.A, u.B);
	}
}
void add(int x, int val){
	s -= (0 < cnt[x]);
	cnt[x] += val;
	s += (0 < cnt[x]);
}
void DFS5(int v){
	if (v <= n)
		ans[v] = s;
	else if (v <= n + n)
		col[v] = c[v - n];
	else
		col[v] = c[P[v - n - n]];
	add(col[v], 1);
	for (int u : g[v])
		DFS5(u);
	add(col[v], - 1);
}

int main(){
	//fast_io;

	cin >> n >> m;
	for (int i = 1; i < n; ++ i){
		int v, u;
		cin >> v >> u;
		adj[v].push_back(u);
		adj[u].push_back(v);
	}
	for (int i = 1; i <= n; ++ i)
		cin >> c[i];
	dmx[1][1] = - 1;
	add_edge(1 + n + n, 0, 0);
	DFS1(1);
	DFS2(1);
	DFS3(1);
	DFS4(0);
	DFS5(0);
	for (int i = 1; i <= n; ++ i)
		cout << ans[i] - 1 << endl;

	return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 33484 KB Output is correct
2 Correct 23 ms 34712 KB Output is correct
3 Correct 20 ms 34196 KB Output is correct
4 Correct 23 ms 34848 KB Output is correct
5 Correct 23 ms 34832 KB Output is correct
6 Correct 23 ms 34972 KB Output is correct
7 Correct 23 ms 34892 KB Output is correct
8 Correct 22 ms 34832 KB Output is correct
9 Correct 22 ms 34780 KB Output is correct
10 Correct 23 ms 34800 KB Output is correct
11 Correct 22 ms 34836 KB Output is correct
12 Correct 25 ms 34892 KB Output is correct
13 Correct 24 ms 34932 KB Output is correct
14 Correct 26 ms 34792 KB Output is correct
15 Correct 24 ms 34896 KB Output is correct
16 Correct 22 ms 34764 KB Output is correct
17 Correct 23 ms 34996 KB Output is correct
18 Correct 23 ms 34840 KB Output is correct
19 Correct 23 ms 34756 KB Output is correct
20 Correct 23 ms 35148 KB Output is correct
21 Correct 24 ms 34916 KB Output is correct
22 Correct 23 ms 34736 KB Output is correct
23 Correct 22 ms 34764 KB Output is correct
24 Correct 24 ms 34816 KB Output is correct
25 Correct 23 ms 34764 KB Output is correct
26 Correct 22 ms 34708 KB Output is correct
27 Correct 23 ms 35056 KB Output is correct
28 Correct 23 ms 35020 KB Output is correct
29 Correct 23 ms 34892 KB Output is correct
30 Correct 23 ms 34764 KB Output is correct
31 Correct 23 ms 34892 KB Output is correct
32 Correct 23 ms 34884 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 107544 KB Output is correct
2 Correct 957 ms 127540 KB Output is correct
3 Correct 139 ms 54340 KB Output is correct
4 Correct 1040 ms 161952 KB Output is correct
5 Correct 1871 ms 187772 KB Output is correct
6 Correct 1455 ms 183312 KB Output is correct
7 Correct 1075 ms 162148 KB Output is correct
8 Correct 1122 ms 165020 KB Output is correct
9 Correct 1035 ms 164276 KB Output is correct
10 Correct 1050 ms 164328 KB Output is correct
11 Correct 876 ms 161564 KB Output is correct
12 Correct 1523 ms 186220 KB Output is correct
13 Correct 1415 ms 173856 KB Output is correct
14 Correct 1373 ms 178136 KB Output is correct
15 Correct 839 ms 160356 KB Output is correct
16 Correct 1471 ms 178764 KB Output is correct
17 Correct 1336 ms 178684 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 813 ms 133392 KB Output is correct
2 Correct 1791 ms 185764 KB Output is correct
3 Correct 152 ms 57592 KB Output is correct
4 Correct 1032 ms 163712 KB Output is correct
5 Correct 1863 ms 191712 KB Output is correct
6 Correct 1392 ms 178340 KB Output is correct
7 Correct 996 ms 163812 KB Output is correct
8 Correct 1131 ms 168696 KB Output is correct
9 Correct 1087 ms 167436 KB Output is correct
10 Correct 1070 ms 166176 KB Output is correct
11 Correct 993 ms 163864 KB Output is correct
12 Correct 1774 ms 183436 KB Output is correct
13 Correct 1290 ms 173140 KB Output is correct
14 Correct 1398 ms 179540 KB Output is correct
15 Correct 883 ms 162076 KB Output is correct
16 Correct 1560 ms 181040 KB Output is correct
17 Correct 1362 ms 178280 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 33484 KB Output is correct
2 Correct 23 ms 34712 KB Output is correct
3 Correct 20 ms 34196 KB Output is correct
4 Correct 23 ms 34848 KB Output is correct
5 Correct 23 ms 34832 KB Output is correct
6 Correct 23 ms 34972 KB Output is correct
7 Correct 23 ms 34892 KB Output is correct
8 Correct 22 ms 34832 KB Output is correct
9 Correct 22 ms 34780 KB Output is correct
10 Correct 23 ms 34800 KB Output is correct
11 Correct 22 ms 34836 KB Output is correct
12 Correct 25 ms 34892 KB Output is correct
13 Correct 24 ms 34932 KB Output is correct
14 Correct 26 ms 34792 KB Output is correct
15 Correct 24 ms 34896 KB Output is correct
16 Correct 22 ms 34764 KB Output is correct
17 Correct 23 ms 34996 KB Output is correct
18 Correct 23 ms 34840 KB Output is correct
19 Correct 23 ms 34756 KB Output is correct
20 Correct 23 ms 35148 KB Output is correct
21 Correct 24 ms 34916 KB Output is correct
22 Correct 23 ms 34736 KB Output is correct
23 Correct 22 ms 34764 KB Output is correct
24 Correct 24 ms 34816 KB Output is correct
25 Correct 23 ms 34764 KB Output is correct
26 Correct 22 ms 34708 KB Output is correct
27 Correct 23 ms 35056 KB Output is correct
28 Correct 23 ms 35020 KB Output is correct
29 Correct 23 ms 34892 KB Output is correct
30 Correct 23 ms 34764 KB Output is correct
31 Correct 23 ms 34892 KB Output is correct
32 Correct 23 ms 34884 KB Output is correct
33 Correct 550 ms 107544 KB Output is correct
34 Correct 957 ms 127540 KB Output is correct
35 Correct 139 ms 54340 KB Output is correct
36 Correct 1040 ms 161952 KB Output is correct
37 Correct 1871 ms 187772 KB Output is correct
38 Correct 1455 ms 183312 KB Output is correct
39 Correct 1075 ms 162148 KB Output is correct
40 Correct 1122 ms 165020 KB Output is correct
41 Correct 1035 ms 164276 KB Output is correct
42 Correct 1050 ms 164328 KB Output is correct
43 Correct 876 ms 161564 KB Output is correct
44 Correct 1523 ms 186220 KB Output is correct
45 Correct 1415 ms 173856 KB Output is correct
46 Correct 1373 ms 178136 KB Output is correct
47 Correct 839 ms 160356 KB Output is correct
48 Correct 1471 ms 178764 KB Output is correct
49 Correct 1336 ms 178684 KB Output is correct
50 Correct 813 ms 133392 KB Output is correct
51 Correct 1791 ms 185764 KB Output is correct
52 Correct 152 ms 57592 KB Output is correct
53 Correct 1032 ms 163712 KB Output is correct
54 Correct 1863 ms 191712 KB Output is correct
55 Correct 1392 ms 178340 KB Output is correct
56 Correct 996 ms 163812 KB Output is correct
57 Correct 1131 ms 168696 KB Output is correct
58 Correct 1087 ms 167436 KB Output is correct
59 Correct 1070 ms 166176 KB Output is correct
60 Correct 993 ms 163864 KB Output is correct
61 Correct 1774 ms 183436 KB Output is correct
62 Correct 1290 ms 173140 KB Output is correct
63 Correct 1398 ms 179540 KB Output is correct
64 Correct 883 ms 162076 KB Output is correct
65 Correct 1560 ms 181040 KB Output is correct
66 Correct 1362 ms 178280 KB Output is correct
67 Correct 113 ms 51088 KB Output is correct
68 Correct 646 ms 108100 KB Output is correct
69 Correct 756 ms 122672 KB Output is correct
70 Correct 982 ms 162092 KB Output is correct
71 Correct 1843 ms 191548 KB Output is correct
72 Correct 1387 ms 181560 KB Output is correct
73 Correct 1010 ms 162116 KB Output is correct
74 Correct 1069 ms 169172 KB Output is correct
75 Correct 1056 ms 164608 KB Output is correct
76 Correct 1029 ms 163640 KB Output is correct
77 Correct 932 ms 162116 KB Output is correct
78 Correct 1703 ms 179752 KB Output is correct
79 Correct 1455 ms 182084 KB Output is correct
80 Correct 1304 ms 178368 KB Output is correct
81 Correct 821 ms 160156 KB Output is correct
82 Correct 1538 ms 189924 KB Output is correct
83 Correct 1378 ms 178564 KB Output is correct
84 Correct 1047 ms 162200 KB Output is correct
85 Correct 1894 ms 197820 KB Output is correct
86 Correct 1405 ms 179720 KB Output is correct
87 Correct 1027 ms 162196 KB Output is correct
88 Correct 1091 ms 169668 KB Output is correct
89 Correct 1074 ms 165424 KB Output is correct
90 Correct 1046 ms 164716 KB Output is correct
91 Correct 948 ms 162960 KB Output is correct
92 Correct 1926 ms 195812 KB Output is correct
93 Correct 1261 ms 173540 KB Output is correct
94 Correct 1208 ms 168252 KB Output is correct
95 Correct 854 ms 160724 KB Output is correct
96 Correct 1539 ms 179412 KB Output is correct
97 Correct 1429 ms 177996 KB Output is correct
98 Correct 1022 ms 163616 KB Output is correct
99 Correct 1897 ms 199748 KB Output is correct
100 Correct 1430 ms 181232 KB Output is correct
101 Correct 1010 ms 162884 KB Output is correct
102 Correct 1082 ms 167796 KB Output is correct
103 Correct 1091 ms 166528 KB Output is correct
104 Correct 1078 ms 164540 KB Output is correct
105 Correct 942 ms 162860 KB Output is correct
106 Correct 1437 ms 183744 KB Output is correct
107 Correct 1458 ms 178500 KB Output is correct
108 Correct 1193 ms 172496 KB Output is correct
109 Correct 922 ms 161736 KB Output is correct
110 Correct 1549 ms 180056 KB Output is correct
111 Correct 1400 ms 178944 KB Output is correct