oj.uz

Submission #359090

# Submission time Handle Problem Language Result Execution time Memory
359090 2021-01-26T10:43:34 Z AmShZ Capital City (JOI20_capital_city) C++11
1 / 100
 1555 ms 524292 KB 
//khodaya khodet komak kon
# pragma GCC target ("avx2")
# pragma GCC optimization ("Ofast")
# pragma GCC optimization ("unroll-loops")
# 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 = 10 + 10;
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;
}

Compilation message

capital_city.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | # pragma GCC optimization ("Ofast")
      | 
capital_city.cpp:4: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    4 | # pragma GCC optimization ("unroll-loops")
      |

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 292460 KB Output is correct
2 Correct 217 ms 292460 KB Output is correct
3 Correct 221 ms 292332 KB Output is correct
4 Correct 225 ms 292608 KB Output is correct
5 Correct 220 ms 292332 KB Output is correct
6 Correct 213 ms 292332 KB Output is correct
7 Correct 215 ms 292320 KB Output is correct
8 Correct 221 ms 292460 KB Output is correct
9 Correct 216 ms 292332 KB Output is correct
10 Correct 228 ms 292332 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 292460 KB Output is correct
2 Correct 217 ms 292460 KB Output is correct
3 Correct 221 ms 292332 KB Output is correct
4 Correct 225 ms 292608 KB Output is correct
5 Correct 220 ms 292332 KB Output is correct
6 Correct 213 ms 292332 KB Output is correct
7 Correct 215 ms 292320 KB Output is correct
8 Correct 221 ms 292460 KB Output is correct
9 Correct 216 ms 292332 KB Output is correct
10 Correct 228 ms 292332 KB Output is correct
11 Correct 229 ms 297824 KB Output is correct
12 Correct 231 ms 297824 KB Output is correct
13 Correct 230 ms 297824 KB Output is correct
14 Correct 241 ms 297824 KB Output is correct
15 Incorrect 235 ms 297952 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 1555 ms 524292 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 231 ms 292460 KB Output is correct
2 Correct 217 ms 292460 KB Output is correct
3 Correct 221 ms 292332 KB Output is correct
4 Correct 225 ms 292608 KB Output is correct
5 Correct 220 ms 292332 KB Output is correct
6 Correct 213 ms 292332 KB Output is correct
7 Correct 215 ms 292320 KB Output is correct
8 Correct 221 ms 292460 KB Output is correct
9 Correct 216 ms 292332 KB Output is correct
10 Correct 228 ms 292332 KB Output is correct
11 Correct 229 ms 297824 KB Output is correct
12 Correct 231 ms 297824 KB Output is correct
13 Correct 230 ms 297824 KB Output is correct
14 Correct 241 ms 297824 KB Output is correct
15 Incorrect 235 ms 297952 KB Output isn't correct
16 Halted 0 ms 0 KB -