oj.uz

Submission #839881

# Submission time Handle Problem Language Result Execution time Memory
839881 2023-08-30T19:22:49 Z NK_ Capital City (JOI20_capital_city) C++17
100 / 100
 606 ms 45632 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl '\n'
#define pb push_back
#define pf push_front
 
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using pi = pair<int, int>;
using vi = V<int>;
using vpi = V<pi>;
 
using ll = long long;
using pl = pair<ll, ll>;
using vpl = V<pl>;
using vl = V<ll>;
 
using db = long double;
 
template<class T> using pq = priority_queue<T, V<T>, less<T>>;
 
const int MOD = 1e9 + 7;
const ll INFL = ll(1e17);
const int LG = 19;

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int N, K; cin >> N >> K;

	V<vi> adj(N), pos(K);

	for(int i = 0; i < N - 1; i++) {
		int u, v; cin >> u >> v; --u, --v;
		adj[u].pb(v); adj[v].pb(u);
	}

	vi A(N); for(auto& x : A) { cin >> x; --x; }

	vi proc(N), sub(N); 
	vi par(N), rt(N), vis(N); 
	vi seen(K), C(K), U;

	for(auto& x : A) C[x]++;

	function<void(int, int)> gen = [&](int u, int p) {
		sub[u] = 1;

		for(auto& v : adj[u]) if (!proc[v] && v != p) {
			gen(v, u);
			sub[u] += sub[v];
		}
	};

	function<void(int, int)> fix = [&](int u, int p) {
		par[u] = p; rt[u] = rt[p]; U.pb(u);
		for(auto& v : adj[u]) if (!proc[v] && v != p) fix(v, u);
	};

	function<int(int, int, int)> find = [&](int u, int p, int n) {
		for(auto& v : adj[u]) if (!proc[v] && v != p) {
			if (2 * sub[v] > n) return find(v, u, n);
		}
		return u;
	};


	int ans = MOD;
	function<void(int)> decomp = [&](int u) {
		gen(u, u); int c = find(u, u, sub[u]);
		rt[c] = c; fix(c, c);

		// cout << "NODES: ";
		for(auto& x : U) {
			// cout << x << " ";
			pos[A[x]].pb(x);
		}
		// cout << endl;


		// cout << "CENTROID: " << c << endl;

		vi have; 
		vis[c] = 1; have.pb(c); 

		int res = 0;
		for(int i = 0; i < sz(have); i++) {
			int x = have[i];
			// cout << "AT: " << x << endl;

			if (!seen[A[x]]) {
				++res;

				if (sz(pos[A[x]]) != C[A[x]]) {
					res = MOD; break;
				}

				for(auto& y : pos[A[x]]) if (!vis[y]) { 
					have.pb(y); vis[y] = 1;
				}
				
				seen[A[x]] = 1;
			}

			if (!vis[par[x]]) {
				have.pb(par[x]);
				vis[par[x]] = 1;
			}
		}

		for(auto& x : U) {
			vis[x] = 0, seen[A[x]] = 0;
			pos[A[x]].pop_back();
			// cout << A[x] << " -> " << sz(pos[A[x]]) << endl;
		}

		U = {};

		// cout << "RES: " << res << endl;

		ans = min(ans, res);

		proc[c] = 1;
		for(auto& v : adj[c]) if (!proc[v]) decomp(v);
	};

	decomp(0);

	cout << ans - 1 << nl;

	exit(0-0);
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 2 ms 468 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 2 ms 596 KB Output is correct
18 Correct 3 ms 596 KB Output is correct
19 Correct 2 ms 596 KB Output is correct
20 Correct 1 ms 596 KB Output is correct
21 Correct 2 ms 596 KB Output is correct
22 Correct 2 ms 724 KB Output is correct
23 Correct 2 ms 596 KB Output is correct
24 Correct 2 ms 596 KB Output is correct
25 Correct 2 ms 596 KB Output is correct
26 Correct 2 ms 596 KB Output is correct
27 Correct 2 ms 596 KB Output is correct
28 Correct 2 ms 596 KB Output is correct
29 Correct 3 ms 596 KB Output is correct
30 Correct 2 ms 596 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 41216 KB Output is correct
2 Correct 183 ms 45500 KB Output is correct
3 Correct 499 ms 44516 KB Output is correct
4 Correct 189 ms 45504 KB Output is correct
5 Correct 437 ms 40948 KB Output is correct
6 Correct 185 ms 45464 KB Output is correct
7 Correct 497 ms 41376 KB Output is correct
8 Correct 188 ms 44864 KB Output is correct
9 Correct 484 ms 39068 KB Output is correct
10 Correct 466 ms 36124 KB Output is correct
11 Correct 501 ms 39640 KB Output is correct
12 Correct 512 ms 43136 KB Output is correct
13 Correct 509 ms 35688 KB Output is correct
14 Correct 498 ms 43176 KB Output is correct
15 Correct 532 ms 42820 KB Output is correct
16 Correct 518 ms 36748 KB Output is correct
17 Correct 486 ms 37404 KB Output is correct
18 Correct 513 ms 37644 KB Output is correct
19 Correct 589 ms 41536 KB Output is correct
20 Correct 486 ms 43972 KB Output is correct
21 Correct 0 ms 212 KB Output is correct

Subtask #4
59.0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 2 ms 468 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 2 ms 596 KB Output is correct
18 Correct 3 ms 596 KB Output is correct
19 Correct 2 ms 596 KB Output is correct
20 Correct 1 ms 596 KB Output is correct
21 Correct 2 ms 596 KB Output is correct
22 Correct 2 ms 724 KB Output is correct
23 Correct 2 ms 596 KB Output is correct
24 Correct 2 ms 596 KB Output is correct
25 Correct 2 ms 596 KB Output is correct
26 Correct 2 ms 596 KB Output is correct
27 Correct 2 ms 596 KB Output is correct
28 Correct 2 ms 596 KB Output is correct
29 Correct 3 ms 596 KB Output is correct
30 Correct 2 ms 596 KB Output is correct
31 Correct 487 ms 41216 KB Output is correct
32 Correct 183 ms 45500 KB Output is correct
33 Correct 499 ms 44516 KB Output is correct
34 Correct 189 ms 45504 KB Output is correct
35 Correct 437 ms 40948 KB Output is correct
36 Correct 185 ms 45464 KB Output is correct
37 Correct 497 ms 41376 KB Output is correct
38 Correct 188 ms 44864 KB Output is correct
39 Correct 484 ms 39068 KB Output is correct
40 Correct 466 ms 36124 KB Output is correct
41 Correct 501 ms 39640 KB Output is correct
42 Correct 512 ms 43136 KB Output is correct
43 Correct 509 ms 35688 KB Output is correct
44 Correct 498 ms 43176 KB Output is correct
45 Correct 532 ms 42820 KB Output is correct
46 Correct 518 ms 36748 KB Output is correct
47 Correct 486 ms 37404 KB Output is correct
48 Correct 513 ms 37644 KB Output is correct
49 Correct 589 ms 41536 KB Output is correct
50 Correct 486 ms 43972 KB Output is correct
51 Correct 0 ms 212 KB Output is correct
52 Correct 363 ms 24140 KB Output is correct
53 Correct 347 ms 24132 KB Output is correct
54 Correct 301 ms 24100 KB Output is correct
55 Correct 304 ms 24116 KB Output is correct
56 Correct 350 ms 24124 KB Output is correct
57 Correct 346 ms 24136 KB Output is correct
58 Correct 347 ms 29216 KB Output is correct
59 Correct 305 ms 29204 KB Output is correct
60 Correct 402 ms 28524 KB Output is correct
61 Correct 445 ms 28448 KB Output is correct
62 Correct 189 ms 45504 KB Output is correct
63 Correct 202 ms 45632 KB Output is correct
64 Correct 189 ms 45160 KB Output is correct
65 Correct 190 ms 45364 KB Output is correct
66 Correct 260 ms 34868 KB Output is correct
67 Correct 287 ms 34704 KB Output is correct
68 Correct 275 ms 34852 KB Output is correct
69 Correct 272 ms 34880 KB Output is correct
70 Correct 261 ms 34764 KB Output is correct
71 Correct 280 ms 34764 KB Output is correct
72 Correct 254 ms 34772 KB Output is correct
73 Correct 265 ms 33808 KB Output is correct
74 Correct 276 ms 34864 KB Output is correct
75 Correct 274 ms 34828 KB Output is correct
76 Correct 386 ms 34088 KB Output is correct
77 Correct 371 ms 31944 KB Output is correct
78 Correct 515 ms 37656 KB Output is correct
79 Correct 606 ms 35240 KB Output is correct
80 Correct 512 ms 43600 KB Output is correct
81 Correct 521 ms 39360 KB Output is correct
82 Correct 534 ms 39516 KB Output is correct
83 Correct 498 ms 35448 KB Output is correct
84 Correct 496 ms 42592 KB Output is correct
85 Correct 494 ms 40948 KB Output is correct
86 Correct 551 ms 35188 KB Output is correct
87 Correct 503 ms 37164 KB Output is correct
88 Correct 463 ms 38156 KB Output is correct
89 Correct 418 ms 33432 KB Output is correct
90 Correct 422 ms 32984 KB Output is correct
91 Correct 423 ms 36124 KB Output is correct
92 Correct 415 ms 34340 KB Output is correct
93 Correct 490 ms 34092 KB Output is correct
94 Correct 418 ms 33336 KB Output is correct
95 Correct 432 ms 35180 KB Output is correct
96 Correct 401 ms 33588 KB Output is correct
97 Correct 426 ms 36220 KB Output is correct