oj.uz

Submission #216906

# Submission time Handle Problem Language Result Execution time Memory
216906 2020-03-28T11:21:49 Z Toadologist Capital City (JOI20_capital_city) C++17
100 / 100
 2636 ms 270268 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#ifdef DEBUG
#define display(x) cerr << #x << " = " << (x) << endl;
#define displaya(a, st, n)\
	{cerr << #a << " = {";\
	for(int qwq = (st); qwq <= (n); ++qwq) {\
		if(qwq == (st)) cerr << ((a)[qwq]);\
		else cerr << ", " << ((a)[qwq]);\
	} cerr << "}" << endl;}
#define displayv(v) displaya(v, 0, (int)(v).size() - 1)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define display(x) ;
#define displaya(a, st, n) ;
#define displayv(v) ;
#define eprintf(...) if(0) fprintf(stderr, "...")
#endif
template<typename T> bool chmin(T &a, const T &b) { return a > b ? a = b, true : false; }
template<typename T> bool chmax(T &a, const T &b) { return a < b ? a = b, true : false; }
template<typename A, typename B>
ostream& operator << (ostream& out, const pair<A, B> &p) {
	return out << '(' << p.first << ", " << p.second << ')';
}
#ifndef LOCAL
char pool[1<<15|1],*it=pool+32768;
#define getchar() (it>=pool+32768?(pool[fread(pool,sizeof(char),\
	1<<15,stdin)]=EOF,*((it=pool)++)):*(it++))
#endif
inline int readint() {
	int a = 0; char c = getchar(), p = 0;
	while(isspace(c)) c = getchar();
	if(c == '-') p = 1, c = getchar();
	while(isdigit(c)) a = a*10 + c - '0', c = getchar();
	return p ? -a : a;
}

const int maxN = 200000 + 5;
int n, k, g[maxN];
vector<int> G[maxN];
vector<int> fam[maxN];
int dep[maxN], f[20][maxN];
int pre[maxN], dfs_clock = 0;

void dfs(int u, int fa) {
	pre[u] = ++dfs_clock;
	for(int v : G[u]) if(v != fa) {
		dep[v] = dep[u] + 1;
		f[0][v] = u;
		dfs(v, u);
	}
}
int lca(int x, int y) {
	if(dep[x] < dep[y]) swap(x, y);
	int delta = dep[x] - dep[y];
	for(int i = 0; i < 20; ++i) if(delta >> i & 1) x = f[i][x];
	for(int i = 19; i >= 0; --i) if(f[i][x] != f[i][y]) x = f[i][x], y = f[i][y];
	return x == y ? x : f[0][x];
}

const int maxM = 200000 * 22 + 5;
const int maxE = 200000 * 22 * 2 + 200000 * 20;
// 20*n + k
int to[maxE], last[maxE], h[maxM], cm = 0;
int ito[maxE], ilast[maxE], ih[maxM];
void link(int x, int y) {
	cm++;
	assert(cm < maxE - 10);
	assert(x < maxM && y < maxM);
	to[cm] = y; last[cm] = h[x]; h[x] = cm;
	ito[cm] = x; ilast[cm] = ih[y]; ih[y] = cm;
}

int encode(int k, int u) {
	return k * n + u;
}

bool vis[maxM];
vector<int> stk;
void dfs1(int u) {
	vis[u] = true;
	for(int i = h[u]; i; i = last[i]) if(!vis[to[i]]) dfs1(to[i]);
//	for(int v : H[u]) if(!vis[v]) dfs1(v);
	stk.push_back(u);
}
int cnt = 0, scc[maxM];
int now[maxM], len = 0;
void dfs2(int u) {
	vis[u] = true; scc[u] = cnt; now[len++] = u;
//	for(int v : iH[u]) if(!vis[v]) dfs2(v);
	for(int i = ih[u]; i; i = ilast[i])
		if(!vis[ito[i]]) dfs2(ito[i]);
}
int solve() {
	int ans = k;
	memset(vis, 0, sizeof(vis));
	for(int u = 1; u <= 20 * n + k; ++u) if(!vis[u]) dfs1(u);
	memset(vis, 0, sizeof(vis));
	while(stk.size()) {
		int u = stk.back(); stk.pop_back();
		if(!vis[u]) {
			++cnt; len = 0;
			dfs2(u);
			int res = 0;
			bool ok = true;
			for(int j = 0; j < len; ++j) {
				int x = now[j];
				res += (x > 20 * n);
				for(int i = h[x]; i; i = last[i])
					ok &= (scc[x] == scc[to[i]]);
			}
//			for(int x : now) for(int y : H[x]) ok &= (scc[x] == scc[y]);
			if(ok && res) chmin(ans, res);
		}
	}
	return ans - 1;
}

int main() {
//	freopen("qwq.txt", "r", stdin);
	n = readint(); k = readint();
	for(int i = 0; i < n - 1; ++i) {
		int x = readint(), y = readint();
		G[x].push_back(y);
		G[y].push_back(x);
	}
	for(int i = 1; i <= n; ++i) g[i] = readint(), fam[g[i]].push_back(i);
	dep[1] = 1; f[0][1] = 0;
	dfs(1, -1);
	for(int k = 1; k < 20; ++k)
		for(int u = 1; u <= n; ++u)
			f[k][u] = f[k - 1][f[k - 1][u]];
	for(int u = 1; u <= n; ++u)
		link(encode(0, u), g[u] + 20 * n);
	for(int k = 1; k < 20; ++k)
		for(int u = 1; u <= n; ++u) if(dep[u] >= (1 << k)) {
			link(encode(k, u), encode(k - 1, u));
			link(encode(k, u), encode(k - 1, f[k - 1][u]));
		}
	for(int t = 1; t <= k; ++t) {
		sort(fam[t].begin(), fam[t].end(), [&](int x, int y) {
			return pre[x] < pre[y];
		});
		for(int i = 0; i + 1 < (int)fam[t].size(); ++i) {
			int u = fam[t][i], v = fam[t][i + 1];
			int w = lca(u, v);
			{
				int delta = dep[u] - dep[w];
				int x = u;
				for(int k = 0; k < 20; ++k) if(delta >> k & 1)
					link(g[u] + 20 * n, encode(k, x)),
					x = f[k][x];
			}
			{
				int delta = dep[v] - dep[w] + 1;
				int x = v;
				for(int k = 0; k < 20; ++k) if(delta >> k & 1)
					link(g[v] + 20 * n, encode(k, x)),
					x = f[k][x];
			}
		}
	}
	cout << solve() << endl;
	return 0;
}

Subtask #1
1.0 / 1.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14208 KB Output is correct
2 Correct 13 ms 14208 KB Output is correct
3 Correct 13 ms 14208 KB Output is correct
4 Correct 13 ms 14208 KB Output is correct
5 Correct 13 ms 14208 KB Output is correct
6 Correct 13 ms 14208 KB Output is correct
7 Correct 13 ms 14208 KB Output is correct
8 Correct 13 ms 14208 KB Output is correct
9 Correct 13 ms 14208 KB Output is correct
10 Correct 13 ms 14208 KB Output is correct
11 Correct 16 ms 15364 KB Output is correct
12 Correct 16 ms 15360 KB Output is correct
13 Correct 16 ms 15360 KB Output is correct
14 Correct 16 ms 15364 KB Output is correct
15 Correct 16 ms 15744 KB Output is correct
16 Correct 16 ms 15616 KB Output is correct
17 Correct 16 ms 15744 KB Output is correct
18 Correct 16 ms 15616 KB Output is correct
19 Correct 16 ms 15616 KB Output is correct
20 Correct 16 ms 15744 KB Output is correct
21 Correct 16 ms 15616 KB Output is correct
22 Correct 16 ms 16000 KB Output is correct
23 Correct 16 ms 15872 KB Output is correct
24 Correct 16 ms 15740 KB Output is correct
25 Correct 16 ms 15744 KB Output is correct
26 Correct 16 ms 15876 KB Output is correct
27 Correct 16 ms 15872 KB Output is correct
28 Correct 16 ms 15744 KB Output is correct
29 Correct 16 ms 15744 KB Output is correct
30 Correct 16 ms 15744 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2636 ms 268076 KB Output is correct
2 Correct 495 ms 270140 KB Output is correct
3 Correct 2548 ms 265576 KB Output is correct
4 Correct 495 ms 270140 KB Output is correct
5 Correct 2039 ms 246468 KB Output is correct
6 Correct 490 ms 269136 KB Output is correct
7 Correct 2248 ms 251844 KB Output is correct
8 Correct 452 ms 257344 KB Output is correct
9 Correct 994 ms 209596 KB Output is correct
10 Correct 936 ms 205572 KB Output is correct
11 Correct 965 ms 210108 KB Output is correct
12 Correct 994 ms 215100 KB Output is correct
13 Correct 1002 ms 205884 KB Output is correct
14 Correct 984 ms 215204 KB Output is correct
15 Correct 1051 ms 215812 KB Output is correct
16 Correct 979 ms 206524 KB Output is correct
17 Correct 1004 ms 206908 KB Output is correct
18 Correct 1000 ms 207132 KB Output is correct
19 Correct 1057 ms 213836 KB Output is correct
20 Correct 917 ms 216628 KB Output is correct
21 Correct 13 ms 14208 KB Output is correct

Subtask #4
59.0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14208 KB Output is correct
2 Correct 13 ms 14208 KB Output is correct
3 Correct 13 ms 14208 KB Output is correct
4 Correct 13 ms 14208 KB Output is correct
5 Correct 13 ms 14208 KB Output is correct
6 Correct 13 ms 14208 KB Output is correct
7 Correct 13 ms 14208 KB Output is correct
8 Correct 13 ms 14208 KB Output is correct
9 Correct 13 ms 14208 KB Output is correct
10 Correct 13 ms 14208 KB Output is correct
11 Correct 16 ms 15364 KB Output is correct
12 Correct 16 ms 15360 KB Output is correct
13 Correct 16 ms 15360 KB Output is correct
14 Correct 16 ms 15364 KB Output is correct
15 Correct 16 ms 15744 KB Output is correct
16 Correct 16 ms 15616 KB Output is correct
17 Correct 16 ms 15744 KB Output is correct
18 Correct 16 ms 15616 KB Output is correct
19 Correct 16 ms 15616 KB Output is correct
20 Correct 16 ms 15744 KB Output is correct
21 Correct 16 ms 15616 KB Output is correct
22 Correct 16 ms 16000 KB Output is correct
23 Correct 16 ms 15872 KB Output is correct
24 Correct 16 ms 15740 KB Output is correct
25 Correct 16 ms 15744 KB Output is correct
26 Correct 16 ms 15876 KB Output is correct
27 Correct 16 ms 15872 KB Output is correct
28 Correct 16 ms 15744 KB Output is correct
29 Correct 16 ms 15744 KB Output is correct
30 Correct 16 ms 15744 KB Output is correct
31 Correct 2636 ms 268076 KB Output is correct
32 Correct 495 ms 270140 KB Output is correct
33 Correct 2548 ms 265576 KB Output is correct
34 Correct 495 ms 270140 KB Output is correct
35 Correct 2039 ms 246468 KB Output is correct
36 Correct 490 ms 269136 KB Output is correct
37 Correct 2248 ms 251844 KB Output is correct
38 Correct 452 ms 257344 KB Output is correct
39 Correct 994 ms 209596 KB Output is correct
40 Correct 936 ms 205572 KB Output is correct
41 Correct 965 ms 210108 KB Output is correct
42 Correct 994 ms 215100 KB Output is correct
43 Correct 1002 ms 205884 KB Output is correct
44 Correct 984 ms 215204 KB Output is correct
45 Correct 1051 ms 215812 KB Output is correct
46 Correct 979 ms 206524 KB Output is correct
47 Correct 1004 ms 206908 KB Output is correct
48 Correct 1000 ms 207132 KB Output is correct
49 Correct 1057 ms 213836 KB Output is correct
50 Correct 917 ms 216628 KB Output is correct
51 Correct 13 ms 14208 KB Output is correct
52 Correct 927 ms 119260 KB Output is correct
53 Correct 934 ms 120252 KB Output is correct
54 Correct 920 ms 119996 KB Output is correct
55 Correct 936 ms 120656 KB Output is correct
56 Correct 931 ms 119792 KB Output is correct
57 Correct 934 ms 120252 KB Output is correct
58 Correct 1020 ms 193080 KB Output is correct
59 Correct 1110 ms 195108 KB Output is correct
60 Correct 1237 ms 193408 KB Output is correct
61 Correct 1218 ms 192444 KB Output is correct
62 Correct 505 ms 270268 KB Output is correct
63 Correct 503 ms 270140 KB Output is correct
64 Correct 463 ms 260436 KB Output is correct
65 Correct 493 ms 268992 KB Output is correct
66 Correct 804 ms 173420 KB Output is correct
67 Correct 761 ms 195072 KB Output is correct
68 Correct 799 ms 173696 KB Output is correct
69 Correct 847 ms 196988 KB Output is correct
70 Correct 839 ms 197116 KB Output is correct
71 Correct 819 ms 173568 KB Output is correct
72 Correct 788 ms 173592 KB Output is correct
73 Correct 774 ms 208020 KB Output is correct
74 Correct 786 ms 173440 KB Output is correct
75 Correct 842 ms 197116 KB Output is correct
76 Correct 758 ms 200124 KB Output is correct
77 Correct 766 ms 191296 KB Output is correct
78 Correct 1035 ms 207044 KB Output is correct
79 Correct 999 ms 205756 KB Output is correct
80 Correct 929 ms 215488 KB Output is correct
81 Correct 977 ms 210080 KB Output is correct
82 Correct 1034 ms 211068 KB Output is correct
83 Correct 988 ms 205904 KB Output is correct
84 Correct 1085 ms 215996 KB Output is correct
85 Correct 999 ms 212224 KB Output is correct
86 Correct 996 ms 205580 KB Output is correct
87 Correct 956 ms 206276 KB Output is correct
88 Correct 1406 ms 211128 KB Output is correct
89 Correct 1359 ms 202920 KB Output is correct
90 Correct 1344 ms 202096 KB Output is correct
91 Correct 1307 ms 204764 KB Output is correct
92 Correct 1403 ms 204868 KB Output is correct
93 Correct 1330 ms 203768 KB Output is correct
94 Correct 1378 ms 203196 KB Output is correct
95 Correct 1334 ms 204756 KB Output is correct
96 Correct 1392 ms 204596 KB Output is correct
97 Correct 1350 ms 205548 KB Output is correct