oj.uz

Submission #359110

# Submission time Handle Problem Language Result Execution time Memory
359110 2021-01-26T11:04:14 Z AmShZ Capital City (JOI20_capital_city) C++11
1 / 100
 1906 ms 524288 KB 
//khodaya khodet komak kon
# include <bits/stdc++.h>
 
/*
// ordered_set 
# include <ext/pb_ds/assoc_container.hpp>
# include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
# define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
*/
 
using namespace std;
 
typedef long long                                        ll;
typedef long double                                      ld;
typedef pair <int, int>                                  pii;
typedef pair <pii, int>                                  ppi;
typedef pair <int, pii>                                  pip;
typedef pair <pii, pii>                                  ppp;
typedef pair <ll, ll>                                    pll;
 
# define A                                               first
# define B                                               second
# define endl                                            '\n'
# define sep                                             ' '
# define all(x)                                          x.begin(), x.end()
# define kill(x)                                         return cout << x << endl, 0
# define SZ(x)                                           int(x.size())
# define lc                                              id << 1
# define rc                                              id << 1 | 1
# define InTheNameOfGod                                  ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
 
ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}
 
const int xn = 2e5 + 10;
const int xm = 18;
const int sq = 320;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const int mod = 1e9 + 7;
const int base = 257;

int n, k, c[xn], par[xm][xn], col[xm][xn], dp[xn * xm];
int H[xn], ans = inf, a[xn * xm], ptr, S;
vector <int> adj[xn], vec[xn], G[2][xn * xm], topo, nei[xn * xm];
vector <pii> E;
bitset <xn * xm> mark;

void add_edge(int v, int u){
	G[0][v].push_back(u);
	G[1][u].push_back(v);
	E.push_back({v, u});
}
void preDFS(int v){
	for (int u : adj[v]){
		if (u == par[0][v])
			continue;
		H[u] = H[v] + 1;
		par[0][u] = v;
		col[0][u] = ++ ptr;
		add_edge(ptr, v);
		preDFS(u);
	}
}
int LCA(int v, int u){
	if (H[v] > H[u])
		swap(v, u);
	for (int i = xm - 1; i >= 0; -- i)
		if ((1 << i) <= H[u] - H[v])
			u = par[i][u];
	if (v == u)
		return v;
	for (int i = xm - 1; i >= 0; -- i)
		if (par[i][v] != par[i][u])
			v = par[i][v], u = par[i][u];
	return par[0][v];
}
void DFS(int v){
	mark[v] = 1;
	for (int u : G[0][v])
		if (!mark[u])
			DFS(u);
	topo.push_back(v);
}
void SFD(int v, int mf){
	mark[v] = 1;
	a[v] = mf;
	for (int u : G[1][v])
		if (!mark[u])
			SFD(u, mf);
}

int main(){
	InTheNameOfGod;
	
	cin >> n >> k, ptr = n;
	for (int i = 0; i < n - 1; ++ i){
		int v, u;
		cin >> v >> u;
		adj[v].push_back(u);
		adj[u].push_back(v);
	}
	for (int i = 1; i <= n; ++ i)
		cin >> c[i], vec[c[i]].push_back(i);
	preDFS(1);
	for (int i = 1; i < xm; ++ i){
		for (int v = 1; v <= n; ++ v){
			par[i][v] = par[i - 1][par[i - 1][v]];
			col[i][v] = ++ ptr;
			add_edge(ptr, col[i - 1][v]);
			add_edge(ptr, col[i - 1][par[i - 1][v]]);
		}
	}
	for (int i = 1; i <= k; ++ i){
		int lca = vec[i][0];
		for (int j = 1; j < SZ(vec[i]); ++ j)
			lca = LCA(lca, vec[i][j]);
		++ ptr;
		for (int u : vec[i]){
			add_edge(ptr, u);
			add_edge(u, ptr);
			int v = u;
			for (int i = xm - 1; i >= 0; -- i){
				if ((1 << i) <= H[v] - H[lca]){
					add_edge(u, col[i][v]);
					v = par[i][v];
				}
			}
		}
	}
	for (int i = 1; i <= ptr; ++ i)
		if (!mark[i])
			DFS(i);
	mark.reset();
	reverse(all(topo));
	for (int v : topo)
		if (!mark[v])
			SFD(v, S ++);
	for (pii e : E){
		int v = e.A, u = e.B;
		if (a[v] != a[u])
			nei[a[v]].push_back(a[u]);
	}
	for (int i = 1; i <= k; ++ i)
		++ dp[a[vec[i][0]]];
	for (int v = S - 1; v >= 0; -- v){
		for (int u : nei[v])
			dp[v] += dp[u];
		if (dp[v])
			ans = min(ans, dp[v] - 1);
	}
	cout << ans << endl;
	
	return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 264068 KB Output is correct
2 Correct 180 ms 264044 KB Output is correct
3 Correct 185 ms 264172 KB Output is correct
4 Correct 187 ms 264044 KB Output is correct
5 Correct 176 ms 264044 KB Output is correct
6 Correct 182 ms 264044 KB Output is correct
7 Correct 188 ms 264044 KB Output is correct
8 Correct 185 ms 264172 KB Output is correct
9 Correct 172 ms 264044 KB Output is correct
10 Correct 172 ms 264044 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 264068 KB Output is correct
2 Correct 180 ms 264044 KB Output is correct
3 Correct 185 ms 264172 KB Output is correct
4 Correct 187 ms 264044 KB Output is correct
5 Correct 176 ms 264044 KB Output is correct
6 Correct 182 ms 264044 KB Output is correct
7 Correct 188 ms 264044 KB Output is correct
8 Correct 185 ms 264172 KB Output is correct
9 Correct 172 ms 264044 KB Output is correct
10 Correct 172 ms 264044 KB Output is correct
11 Correct 196 ms 268992 KB Output is correct
12 Correct 193 ms 268896 KB Output is correct
13 Correct 192 ms 268896 KB Output is correct
14 Correct 191 ms 268896 KB Output is correct
15 Incorrect 198 ms 269024 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 1906 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 264068 KB Output is correct
2 Correct 180 ms 264044 KB Output is correct
3 Correct 185 ms 264172 KB Output is correct
4 Correct 187 ms 264044 KB Output is correct
5 Correct 176 ms 264044 KB Output is correct
6 Correct 182 ms 264044 KB Output is correct
7 Correct 188 ms 264044 KB Output is correct
8 Correct 185 ms 264172 KB Output is correct
9 Correct 172 ms 264044 KB Output is correct
10 Correct 172 ms 264044 KB Output is correct
11 Correct 196 ms 268992 KB Output is correct
12 Correct 193 ms 268896 KB Output is correct
13 Correct 192 ms 268896 KB Output is correct
14 Correct 191 ms 268896 KB Output is correct
15 Incorrect 198 ms 269024 KB Output isn't correct
16 Halted 0 ms 0 KB -