oj.uz

Submission #462589

# Submission time Handle Problem Language Result Execution time Memory
462589 2021-08-10T20:40:20 Z arwaeystoamneg Capital City (JOI20_capital_city) C++17
100 / 100
 1079 ms 44244 KB 
// EXPLOSION!
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define cont continue
#define endl '\n'
//#define ednl '\n'
#define test int testc;cin>>testc;while(testc--)
#define pr(a, b) trav(x,a)cerr << x << b; cerr << endl;
#define message cout << "Hello World" << endl;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const ll inf = 1000000007;//998244353    

void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
	F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef arwaeystoamneg
	if (sz(s))
	{
		freopen((s + ".in").c_str(), "r", stdin);
		if (s != "test1")
			freopen((s + ".out").c_str(), "w", stdout);
	}
#endif
}
int n, k, c, ans;
vector<vi>adj, cadj;
vi visited, sizes, parent, co, depth, up, v;
struct centroid
{
	void dfs(int i, int p)
	{
		// visit i
		sizes[i] = 1;
		for (auto x : adj[i])
		{
			if (x == p || visited[i] == 1)
				continue;
			dfs(x, i);
			sizes[i] += sizes[x];
		}
	}
	int dfs_centroid(int i, int p, int n)
	{
		// visit i, find the centroid c
		// recurrent if i has a subtree larger than n/2;
		for (auto x : adj[i])
		{
			if (x == p)
				continue;
			if (sizes[x] > n / 2)
				return dfs_centroid(x, i, n);
		}
		return i;
	}
	void build(int i, int p)
	{
		// first dfs to generate size of subtree starting from node i
		// 2nd dfs to find the centroid
		dfs(i, p);
		int centroid = dfs_centroid(i, p, sizes[i]);
		visited[centroid] = 1;
		parent[centroid] = p;
		//cout << centroid << endl;
		// remove the edge from centroid to all its child, build from its child
		for (auto x : adj[centroid])
		{
			if (x == parent[centroid])
				continue;
			//cout << "working on subtree of " << x << endl;
			if (visited[x])
				continue;
			build(x, centroid);
		}
	}
	void init()
	{
		n = sz(adj);
		visited.rsz(n);
		sizes.rsz(n);
		parent.rsz(n);
		build(0, -1);
	}
};

vi a;
void read()
{
	cin >> n >> k;
	adj.rsz(n);
	F0R(i, n - 1)
	{
		int x, y;
		cin >> x >> y;
		x--, y--;
		adj[x].pb(y);
		adj[y].pb(x);
	}
	a.rsz(n);
	trav(x, a)cin >> x, x--;
}
void prep()
{
	co.rsz(k);
	F0R(i, n)co[a[i]]++;
}
void cent()
{
	centroid g;
	g.init();
	cadj.rsz(n);
	F0R(i, n)if (parent[i] != -1)cadj[parent[i]].pb(i); else c = i;
}
vector<vi>b;
vi toclear;
void init(int i, int p, int d)
{
	toclear.pb(a[i]);
	v[i] = 0;
	up[i] = p;
	b[a[i]].pb(i);
	trav(x, adj[i])
	{
		if (x == p || depth[x] < d)continue;
		init(x, i, d);
	}
}
void dfs_centroid(int i, int p, int d)
{
	depth[i] = d;
	trav(x, cadj[i])
	{
		if (x == p)continue;
		dfs_centroid(x, i, d + 1);
	}
	toclear.clear();
	init(i, -1, d);
	int cur = 0;
	vi todo = { a[i] };
	v[i] = 1;
	while (sz(todo))
	{
		int x = todo.back();
		todo.pop_back();
		if (sz(b[x]) == 0)continue;
		cur++;
		if (co[x] > sz(b[x])) { cur = inf; break; }
		trav(y, b[x])
		{
			int t = y;
			while (!v[t])
			{
				todo.pb(a[t]);
				v[t] = 1;
				t = up[t];
			}
		}
		b[x].clear();
	}
	trav(x, toclear)b[x].clear();
	ans = min(ans, cur - 1);
}
int main()
{
	setIO("test1");
	read();
	prep();
	cent();
	depth.rsz(n);
	up.rsz(n);
	v.rsz(n);
	b.rsz(k);
	ans = inf;
	dfs_centroid(c, -1, 0);
	cout << ans << endl;
}

Subtask #1
1.0 / 1.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 897 ms 43972 KB Output is correct
2 Correct 293 ms 44244 KB Output is correct
3 Correct 932 ms 43724 KB Output is correct
4 Correct 302 ms 44196 KB Output is correct
5 Correct 904 ms 42080 KB Output is correct
6 Correct 289 ms 44076 KB Output is correct
7 Correct 915 ms 41840 KB Output is correct
8 Correct 288 ms 43312 KB Output is correct
9 Correct 913 ms 40484 KB Output is correct
10 Correct 952 ms 40632 KB Output is correct
11 Correct 959 ms 40572 KB Output is correct
12 Correct 961 ms 41712 KB Output is correct
13 Correct 920 ms 40524 KB Output is correct
14 Correct 947 ms 41976 KB Output is correct
15 Correct 954 ms 41844 KB Output is correct
16 Correct 980 ms 40728 KB Output is correct
17 Correct 957 ms 40800 KB Output is correct
18 Correct 953 ms 40580 KB Output is correct
19 Correct 982 ms 41200 KB Output is correct
20 Correct 995 ms 42244 KB Output is correct
21 Correct 0 ms 204 KB Output is correct

Subtask #4
59.0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 3 ms 588 KB Output is correct
12 Correct 3 ms 588 KB Output is correct
13 Correct 4 ms 588 KB Output is correct
14 Correct 3 ms 588 KB Output is correct
15 Correct 3 ms 588 KB Output is correct
16 Correct 3 ms 588 KB Output is correct
17 Correct 2 ms 588 KB Output is correct
18 Correct 2 ms 588 KB Output is correct
19 Correct 2 ms 588 KB Output is correct
20 Correct 2 ms 588 KB Output is correct
21 Correct 2 ms 580 KB Output is correct
22 Correct 3 ms 716 KB Output is correct
23 Correct 3 ms 716 KB Output is correct
24 Correct 3 ms 588 KB Output is correct
25 Correct 4 ms 588 KB Output is correct
26 Correct 3 ms 716 KB Output is correct
27 Correct 3 ms 588 KB Output is correct
28 Correct 3 ms 588 KB Output is correct
29 Correct 3 ms 588 KB Output is correct
30 Correct 3 ms 588 KB Output is correct
31 Correct 897 ms 43972 KB Output is correct
32 Correct 293 ms 44244 KB Output is correct
33 Correct 932 ms 43724 KB Output is correct
34 Correct 302 ms 44196 KB Output is correct
35 Correct 904 ms 42080 KB Output is correct
36 Correct 289 ms 44076 KB Output is correct
37 Correct 915 ms 41840 KB Output is correct
38 Correct 288 ms 43312 KB Output is correct
39 Correct 913 ms 40484 KB Output is correct
40 Correct 952 ms 40632 KB Output is correct
41 Correct 959 ms 40572 KB Output is correct
42 Correct 961 ms 41712 KB Output is correct
43 Correct 920 ms 40524 KB Output is correct
44 Correct 947 ms 41976 KB Output is correct
45 Correct 954 ms 41844 KB Output is correct
46 Correct 980 ms 40728 KB Output is correct
47 Correct 957 ms 40800 KB Output is correct
48 Correct 953 ms 40580 KB Output is correct
49 Correct 982 ms 41200 KB Output is correct
50 Correct 995 ms 42244 KB Output is correct
51 Correct 0 ms 204 KB Output is correct
52 Correct 692 ms 31876 KB Output is correct
53 Correct 708 ms 31992 KB Output is correct
54 Correct 705 ms 31832 KB Output is correct
55 Correct 712 ms 31896 KB Output is correct
56 Correct 728 ms 31792 KB Output is correct
57 Correct 699 ms 32000 KB Output is correct
58 Correct 721 ms 36212 KB Output is correct
59 Correct 677 ms 36052 KB Output is correct
60 Correct 829 ms 35492 KB Output is correct
61 Correct 891 ms 35440 KB Output is correct
62 Correct 292 ms 44016 KB Output is correct
63 Correct 294 ms 44112 KB Output is correct
64 Correct 291 ms 43488 KB Output is correct
65 Correct 295 ms 44104 KB Output is correct
66 Correct 502 ms 37780 KB Output is correct
67 Correct 498 ms 37636 KB Output is correct
68 Correct 514 ms 37724 KB Output is correct
69 Correct 507 ms 37684 KB Output is correct
70 Correct 528 ms 37724 KB Output is correct
71 Correct 491 ms 37620 KB Output is correct
72 Correct 505 ms 37588 KB Output is correct
73 Correct 552 ms 37664 KB Output is correct
74 Correct 553 ms 37692 KB Output is correct
75 Correct 486 ms 37656 KB Output is correct
76 Correct 942 ms 38204 KB Output is correct
77 Correct 796 ms 37968 KB Output is correct
78 Correct 1008 ms 40648 KB Output is correct
79 Correct 948 ms 40684 KB Output is correct
80 Correct 948 ms 42132 KB Output is correct
81 Correct 925 ms 40532 KB Output is correct
82 Correct 940 ms 40696 KB Output is correct
83 Correct 980 ms 40580 KB Output is correct
84 Correct 1079 ms 41688 KB Output is correct
85 Correct 1022 ms 40888 KB Output is correct
86 Correct 911 ms 40664 KB Output is correct
87 Correct 924 ms 40768 KB Output is correct
88 Correct 827 ms 39084 KB Output is correct
89 Correct 833 ms 38112 KB Output is correct
90 Correct 826 ms 38100 KB Output is correct
91 Correct 855 ms 38076 KB Output is correct
92 Correct 880 ms 38064 KB Output is correct
93 Correct 853 ms 38116 KB Output is correct
94 Correct 835 ms 38040 KB Output is correct
95 Correct 816 ms 38188 KB Output is correct
96 Correct 834 ms 38016 KB Output is correct
97 Correct 822 ms 38244 KB Output is correct