oj.uz

Submission #609602

# Submission time Handle Problem Language Result Execution time Memory
609602 2022-07-27T17:56:39 Z penguinhacker Capital City (JOI20_capital_city) C++17
31 / 100
 683 ms 146628 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ar array
 
const int mxN=2e5, MX=1e6;
int n, k, c[mxN], n2;
int d[mxN], s[mxN], p[mxN], hd[mxN], tin[mxN], tin2[mxN], chain[mxN];
int who[mxN], cnt[mxN];
vector<int> oc[mxN], adj1[mxN], adj2[MX], adj3[MX], st, nodes;
bool vis[MX], out[MX];
 
void dfs1(int u=0) {
	s[u]=1;
	for (int& v : adj1[u]) {
		adj1[v].erase(find(adj1[v].begin(), adj1[v].end(), u));
		d[v]=d[u]+1, p[v]=u;
		dfs1(v);
		s[u]+=s[v];
		if (s[v]>s[adj1[u][0]])
			swap(v, adj1[u][0]);
	}
}

void dfs2(int u=0, int h=0) {
	static int timer=0;
	hd[u]=h, tin[u]=timer++, tin2[tin[u]]=u;
	if (adj1[u].empty())
		return;
	dfs2(adj1[u][0], h);
	for (int i=1; i<adj1[u].size(); ++i)
		dfs2(adj1[u][i], adj1[u][i]);
}

int lca(int u, int v) {
	for (; hd[u]!=hd[v]; v=p[hd[v]])
		if (d[hd[u]]>d[hd[v]])
			swap(u, v);
	return d[u]<d[v]?u:v;
}

void ae(int u, int v) {
	adj2[u].push_back(v);
	adj3[v].push_back(u);
}

void bld(int u=1, int l=0, int r=n-1) {
	if (l==r) {
		ae(u+k, c[tin2[l]]);
		n2=max(n2, u+k+1);
		return;
	}
	int mid=(l+r)/2;
	ae(u+k, 2*u+k);
	ae(u+k, 2*u+1+k);
	bld(2*u, l, mid);
	bld(2*u+1, mid+1, r);
}

void qry(int ql, int qr, int u=1, int l=0, int r=n-1) {
	if (l>qr||r<ql)
		return;
	if (ql<=l&&r<=qr) {
		nodes.push_back(u+k);
		return;
	}
	int mid=(l+r)/2;
	qry(ql, qr, 2*u, l, mid);
	qry(ql, qr, 2*u+1, mid+1, r);
}

void dfs3(int u) {
	vis[u]=1;
	for (int v : adj2[u])
		if (!vis[v])
			dfs3(v);
	st.push_back(u);
}

void dfs4(int u, int rt) {
	vis[u]=0, who[u]=rt;
	cnt[rt]+=u<k;
	for (int v : adj3[u])
		if (vis[v])
			dfs4(v, rt);
}
 
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();
	dfs2();
	bld();
	for (int i=0; i<n; ++i) {
		if (adj1[i].empty()) {
			nodes.clear();
			qry(tin[hd[i]], tin[i]);
			for (int j : nodes)
				ae(n2, j);
			chain[hd[i]]=n2;
			++n2;
		}
	}
	for (int i=0; i<k; ++i) {
		int l=oc[i][0];
		for (int j=1; j<oc[i].size(); ++j)
			l=lca(l, oc[i][j]);
		for (int u : oc[i]) {
			nodes.clear();
			qry(hd[u]==hd[l]?tin[l]:tin[hd[u]],  tin[u]);
			for (int j : nodes)
				ae(i, j);
			if (hd[u]!=hd[l]) {
				for (u=p[hd[u]]; hd[u]!=hd[l]; u=p[hd[u]])
					ae(i, chain[hd[u]]);
				nodes.clear();
				qry(tin[l], tin[u]);
				for (int j : nodes)
					ae(i, j);
			}
		}
	} 
	for (int i=0; i<n2; ++i)
		if (!vis[i])
			dfs3(i);
	reverse(st.begin(), st.end());
	for (int i : st)
		if (vis[i])
			dfs4(i, i);
	for (int i : st)
		for (int j : adj2[i])
			if (who[i]!=who[j])
				out[who[i]]=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 'void dfs2(int, int)':
capital_city.cpp:32:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  for (int i=1; i<adj1[u].size(); ++i)
      |                ~^~~~~~~~~~~~~~~
capital_city.cpp: In function 'int main()':
capital_city.cpp:118:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |   for (int j=1; j<oc[i].size(); ++j)
      |                 ~^~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 56652 KB Output is correct
2 Correct 28 ms 56680 KB Output is correct
3 Correct 28 ms 56728 KB Output is correct
4 Correct 31 ms 56660 KB Output is correct
5 Correct 27 ms 56648 KB Output is correct
6 Correct 27 ms 56652 KB Output is correct
7 Correct 26 ms 56660 KB Output is correct
8 Correct 27 ms 56660 KB Output is correct
9 Correct 30 ms 56660 KB Output is correct
10 Correct 27 ms 56680 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 56652 KB Output is correct
2 Correct 28 ms 56680 KB Output is correct
3 Correct 28 ms 56728 KB Output is correct
4 Correct 31 ms 56660 KB Output is correct
5 Correct 27 ms 56648 KB Output is correct
6 Correct 27 ms 56652 KB Output is correct
7 Correct 26 ms 56660 KB Output is correct
8 Correct 27 ms 56660 KB Output is correct
9 Correct 30 ms 56660 KB Output is correct
10 Correct 27 ms 56680 KB Output is correct
11 Incorrect 29 ms 57424 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 683 ms 146308 KB Output is correct
2 Correct 411 ms 146444 KB Output is correct
3 Correct 667 ms 145908 KB Output is correct
4 Correct 420 ms 146464 KB Output is correct
5 Correct 653 ms 143240 KB Output is correct
6 Correct 412 ms 146628 KB Output is correct
7 Correct 656 ms 143324 KB Output is correct
8 Correct 394 ms 143916 KB Output is correct
9 Correct 563 ms 132508 KB Output is correct
10 Correct 562 ms 131696 KB Output is correct
11 Correct 556 ms 132536 KB Output is correct
12 Correct 548 ms 136276 KB Output is correct
13 Correct 626 ms 128424 KB Output is correct
14 Correct 555 ms 135688 KB Output is correct
15 Correct 555 ms 135588 KB Output is correct
16 Correct 583 ms 134064 KB Output is correct
17 Correct 582 ms 134260 KB Output is correct
18 Correct 567 ms 132056 KB Output is correct
19 Correct 595 ms 135392 KB Output is correct
20 Correct 567 ms 138220 KB Output is correct
21 Correct 27 ms 56660 KB Output is correct

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 56652 KB Output is correct
2 Correct 28 ms 56680 KB Output is correct
3 Correct 28 ms 56728 KB Output is correct
4 Correct 31 ms 56660 KB Output is correct
5 Correct 27 ms 56648 KB Output is correct
6 Correct 27 ms 56652 KB Output is correct
7 Correct 26 ms 56660 KB Output is correct
8 Correct 27 ms 56660 KB Output is correct
9 Correct 30 ms 56660 KB Output is correct
10 Correct 27 ms 56680 KB Output is correct
11 Incorrect 29 ms 57424 KB Output isn't correct
12 Halted 0 ms 0 KB -