oj.uz

Submission #595747

# Submission time Handle Problem Language Result Execution time Memory
595747 2022-07-14T05:49:38 Z penguinhacker Capital City (JOI20_capital_city) C++17
11 / 100
 3000 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ar array
 
const int mxN=2e5;
int n, k, c[mxN], d[mxN], anc[mxN][18], tin[mxN], t, who[20*mxN], cnt[20*mxN];
vector<int> oc[mxN], adj1[mxN], adj2[20*mxN], adj3[20*mxN], st;
bool vis[20*mxN], out[20*mxN];
 
void dfs1(int u=0) {
	tin[u]=t++;
	for (int i=1; i<18; ++i)
		anc[u][i]=anc[anc[u][i-1]][i-1];
	for (int v : adj1[u])
		if (v!=anc[u][0]) {
			d[v]=d[u]+1, anc[v][0]=u;
			dfs1(v);
		}
}
 
int lca(int u, int v) {
	if (d[u]>d[v])
		swap(u, v);
	for (int i=17; ~i; --i)
		if (d[v]-(1<<i)>=d[u])
			v=anc[v][i];
	if (u==v)
		return u;
	for (int i=17; ~i; --i)
		if (anc[u][i]!=anc[v][i])
			u=anc[u][i], v=anc[v][i];
	return anc[u][0];
}
 
void dfs2(int u) {
	vis[u]=1;
	for (int v : adj2[u])
		if (!vis[v])
			dfs2(v);
	st.push_back(u);
}
 
void dfs3(int u, int rt) {
	vis[u]=0, who[u]=rt;
	cnt[rt]+=u<k;
	for (int v : adj3[u])
		if (vis[v])
			dfs3(v, rt);
}
 
void ae(int u, int v) {
	adj2[u].push_back(v);
	adj3[v].push_back(u);
}
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> k;
	for (int i=1; i<n; ++i) {
		int u, v;
		cin >> u >> v, --u, --v;
		adj1[u].push_back(v);
		adj1[v].push_back(u);
	}
	for (int i=0; i<n; ++i) {
		cin >> c[i], --c[i];
		oc[c[i]].push_back(i);
	}
	dfs1();
	for (int i=0; i<n; ++i)
		vector<int>().swap(adj1[i]);
	for (int i=0; i<k; ++i) {
		sort(oc[i].begin(), oc[i].end(), [&](int a, int b) { return tin[a]<tin[b]; } );
		for (int j=1; j<oc[i].size(); ++j) {
			int u=oc[i][j-1], v=oc[i][j];
			int uv=lca(u, v);
			ae(i, c[uv]);
			for (int rep=0; rep<2; ++rep) {
				for (int j=17; ~j; --j)
					if (d[u]-(1<<j)>=d[uv]) {
						ae(i, j*n+u+k);
						u=anc[u][j];
					}
				swap(u, v);
			}
		}
		vector<int>().swap(oc[i]);
	}
	for (int i=0; i<n; ++i) {
		ae(i+k, c[i]);
		for (int j=1; j<18; ++j) {
			ae(j*n+i+k, (j-1)*n+i+k);
			ae(j*n+i+k, (j-1)*n+anc[i][j-1]+k);
		}
	}
	st.reserve(20*n);
	for (int i=0; i<k+18*n; ++i)
		if (!vis[i])
			dfs2(i);
	for (int i=0; i<k+18*n; ++i)
		vector<int>().swap(adj2[i]);
	reverse(st.begin(), st.end());
	for (int i : st)
		if (vis[i])
			dfs3(i, i);
	for (int i : st)
		for (int j : adj3[i])
			if (who[i]!=who[j])
				out[who[j]]=1;
	int ans=69696969;
	for (int i=0; i<k; ++i)
		if (!out[who[i]])
			ans=min(ans, cnt[who[i]]-1);
	cout << ans;
	return 0;
}

Compilation message

capital_city.cpp: In function 'int main()':
capital_city.cpp:77:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   for (int j=1; j<oc[i].size(); ++j) {
      |                 ~^~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 197640 KB Output is correct
2 Correct 90 ms 197552 KB Output is correct
3 Correct 100 ms 197624 KB Output is correct
4 Correct 101 ms 197580 KB Output is correct
5 Correct 89 ms 197524 KB Output is correct
6 Correct 95 ms 197640 KB Output is correct
7 Correct 92 ms 197640 KB Output is correct
8 Correct 99 ms 197520 KB Output is correct
9 Correct 94 ms 197544 KB Output is correct
10 Correct 90 ms 197536 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 197640 KB Output is correct
2 Correct 90 ms 197552 KB Output is correct
3 Correct 100 ms 197624 KB Output is correct
4 Correct 101 ms 197580 KB Output is correct
5 Correct 89 ms 197524 KB Output is correct
6 Correct 95 ms 197640 KB Output is correct
7 Correct 92 ms 197640 KB Output is correct
8 Correct 99 ms 197520 KB Output is correct
9 Correct 94 ms 197544 KB Output is correct
10 Correct 90 ms 197536 KB Output is correct
11 Correct 102 ms 200704 KB Output is correct
12 Correct 105 ms 200616 KB Output is correct
13 Correct 126 ms 200652 KB Output is correct
14 Correct 116 ms 200628 KB Output is correct
15 Correct 101 ms 200624 KB Output is correct
16 Correct 102 ms 200620 KB Output is correct
17 Correct 102 ms 200648 KB Output is correct
18 Correct 121 ms 200680 KB Output is correct
19 Correct 109 ms 200700 KB Output is correct
20 Correct 100 ms 200652 KB Output is correct
21 Correct 100 ms 200644 KB Output is correct
22 Correct 103 ms 200736 KB Output is correct
23 Correct 118 ms 200880 KB Output is correct
24 Correct 103 ms 200664 KB Output is correct
25 Correct 103 ms 200584 KB Output is correct
26 Correct 103 ms 200672 KB Output is correct
27 Correct 109 ms 200664 KB Output is correct
28 Correct 110 ms 200652 KB Output is correct
29 Correct 111 ms 200580 KB Output is correct
30 Correct 103 ms 200648 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3057 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 197640 KB Output is correct
2 Correct 90 ms 197552 KB Output is correct
3 Correct 100 ms 197624 KB Output is correct
4 Correct 101 ms 197580 KB Output is correct
5 Correct 89 ms 197524 KB Output is correct
6 Correct 95 ms 197640 KB Output is correct
7 Correct 92 ms 197640 KB Output is correct
8 Correct 99 ms 197520 KB Output is correct
9 Correct 94 ms 197544 KB Output is correct
10 Correct 90 ms 197536 KB Output is correct
11 Correct 102 ms 200704 KB Output is correct
12 Correct 105 ms 200616 KB Output is correct
13 Correct 126 ms 200652 KB Output is correct
14 Correct 116 ms 200628 KB Output is correct
15 Correct 101 ms 200624 KB Output is correct
16 Correct 102 ms 200620 KB Output is correct
17 Correct 102 ms 200648 KB Output is correct
18 Correct 121 ms 200680 KB Output is correct
19 Correct 109 ms 200700 KB Output is correct
20 Correct 100 ms 200652 KB Output is correct
21 Correct 100 ms 200644 KB Output is correct
22 Correct 103 ms 200736 KB Output is correct
23 Correct 118 ms 200880 KB Output is correct
24 Correct 103 ms 200664 KB Output is correct
25 Correct 103 ms 200584 KB Output is correct
26 Correct 103 ms 200672 KB Output is correct
27 Correct 109 ms 200664 KB Output is correct
28 Correct 110 ms 200652 KB Output is correct
29 Correct 111 ms 200580 KB Output is correct
30 Correct 103 ms 200648 KB Output is correct
31 Execution timed out 3057 ms 524288 KB Time limit exceeded
32 Halted 0 ms 0 KB -