oj.uz

Submission #381662

# Submission time Handle Problem Language Result Execution time Memory
381662 2021-03-25T13:48:30 Z Return_0 Capital City (JOI20_capital_city) C++17
11 / 100
 3000 ms 42452 KB 
#pragma GCC optimize("Ofast,unroll-loops")
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef int ll;
typedef long double ld;
typedef pair <ll, ll> pll;

#ifdef SINA
#define dbg(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1> void __f(const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << std::endl; }
template <typename Arg1, typename... Args> void __f (const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...); }
#define dbg2(x, j, n) cout<< #x << " : "; output((j), (n), x, 1); cout.flush();
#else
#define dbg(...) 0
#define dbg2(x, j, n) 0
#endif
#define SZ(x) ((ll)((x).size()))
#define File(s, t) freopen(s ".txt", "r", stdin); freopen(t ".txt", "w", stdout);
#define input(j, n, a) for (int _i = (j); _i < (n)+(j); _i++) cin>> a[_i];
#define output(j, n, a, t) for (int _i = (j); _i < (n)+(j); _i++) cout<< a[_i] << (((t) && _i != (n)+(j)-1)? ' ' : '\n');
#define kill(x) return cout<< (x) << endl, 0
#define cl const ll
#define fr first
#define sc second
#define lc (v << 1)
#define rc (lc | 1)
#define mid ((l + r) >> 1)
#define All(x) (x).begin(), (x).end()

cl inf = sizeof(ll) == 4 ? (1e9 + 10) : (3e18), mod = 1e9 + 7, MOD = 998244353;

template <class A,class B> ostream& operator << (ostream& out,const pair<A,B>&a){return out<<'('<<a.first<<", "<<a.second<<')';}
template <class A> ostream& operator << (ostream& out, const vector<A> &a) {
	out<< '['; for (int i = -1; ++i < int(a.size());) out<< a[i] << (i + 1 < int(a.size()) ? ", " : ""); return out<<']'; }
template <class T, typename _t = less <T> > using Tree = tree <T, null_type, _t, rb_tree_tag, tree_order_statistics_node_update>;

cl N = 2e5 + 7;

ll C [N], sz [N], mark [N], q [N], par [N], iter [N], R, n, k, sum, ans, tar;
bool hide [N], hide_color [N];
vector <ll> adj [N], col [N];

ll plant (cl &v, cl &pr = 0) {
	sz[v] = 1;
	for (auto &u : adj[v]) if (!hide[u] && u != pr) sz[v] += plant(u, v);
	return sz[v];
}

inline ll find_centroid (ll v, cl &S, ll pr = 0) {
	for (ll i = 0; i < SZ(adj[v]); i++) {
		ll &u = adj[v][i];
		if (sz[u] << 1 > S && !hide[u] && u != pr) pr = v, v = u, i = -1;
	}
	return v;
}

void dfs (cl &v, cl &pr = 0) {
	par[v] = pr;
	iter[v] = tar;
	for (auto &u : adj[v]) if (!hide_color[C[u]] && u != pr) dfs(u, v);
}

void centroid_decomposition (ll v = 1) {
	v = find_centroid(v, plant(v));
	if (!hide_color[C[v]]) {
		tar = C[v]; sum = -1;
		dfs(v);
		R = 1; q[0] = C[v]; mark[0] = mark[C[v]] = tar;
		for (ll l = 0; l < R; l++) {
			sum++;
			for (auto &u : col[q[l]]) {
				if (iter[u] != tar) sum = n;
				if (mark[C[par[u]]] != tar) q[R++] = C[par[u]], mark[C[par[u]]] = tar;
			}
		}
		ans = min(ans, sum);
	}
	hide_color[C[v]] = hide[v] = true;
	for (auto &u : adj[v]) if (!hide[u]) centroid_decomposition(u);
}

int main ()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin>> n >> k;
	for (ll i = 1, v, u; i < n; i++) {
		cin>> v >> u;
		adj[v].push_back(u);
		adj[u].push_back(v);
	}
	for (ll i = 1; i <= n; i++) {
		cin>> C[i];
		col[C[i]].push_back(i);
	}

	ans = n;
	centroid_decomposition();

	cout<< ans << endl;

	cerr<< "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";

	return 0;
}
/*

*/

Subtask #1
1.0 / 1.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9836 KB Output is correct
2 Correct 7 ms 9836 KB Output is correct
3 Correct 7 ms 9836 KB Output is correct
4 Correct 7 ms 9836 KB Output is correct
5 Correct 7 ms 9836 KB Output is correct
6 Correct 7 ms 9836 KB Output is correct
7 Correct 7 ms 9856 KB Output is correct
8 Correct 7 ms 9836 KB Output is correct
9 Correct 7 ms 9836 KB Output is correct
10 Correct 7 ms 9836 KB Output is correct
11 Correct 12 ms 9964 KB Output is correct
12 Correct 12 ms 9964 KB Output is correct
13 Correct 14 ms 9964 KB Output is correct
14 Correct 12 ms 9964 KB Output is correct
15 Correct 11 ms 9964 KB Output is correct
16 Correct 11 ms 9964 KB Output is correct
17 Correct 11 ms 9964 KB Output is correct
18 Correct 9 ms 9964 KB Output is correct
19 Correct 10 ms 9964 KB Output is correct
20 Correct 9 ms 9964 KB Output is correct
21 Correct 9 ms 9964 KB Output is correct
22 Correct 15 ms 10092 KB Output is correct
23 Correct 23 ms 9964 KB Output is correct
24 Correct 17 ms 9964 KB Output is correct
25 Correct 13 ms 10092 KB Output is correct
26 Correct 14 ms 10092 KB Output is correct
27 Correct 12 ms 10096 KB Output is correct
28 Correct 11 ms 9964 KB Output is correct
29 Correct 12 ms 9964 KB Output is correct
30 Correct 11 ms 9964 KB Output is correct

Subtask #3
0 / 30.0

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

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9836 KB Output is correct
2 Correct 7 ms 9836 KB Output is correct
3 Correct 7 ms 9836 KB Output is correct
4 Correct 7 ms 9836 KB Output is correct
5 Correct 7 ms 9836 KB Output is correct
6 Correct 7 ms 9836 KB Output is correct
7 Correct 7 ms 9856 KB Output is correct
8 Correct 7 ms 9836 KB Output is correct
9 Correct 7 ms 9836 KB Output is correct
10 Correct 7 ms 9836 KB Output is correct
11 Correct 12 ms 9964 KB Output is correct
12 Correct 12 ms 9964 KB Output is correct
13 Correct 14 ms 9964 KB Output is correct
14 Correct 12 ms 9964 KB Output is correct
15 Correct 11 ms 9964 KB Output is correct
16 Correct 11 ms 9964 KB Output is correct
17 Correct 11 ms 9964 KB Output is correct
18 Correct 9 ms 9964 KB Output is correct
19 Correct 10 ms 9964 KB Output is correct
20 Correct 9 ms 9964 KB Output is correct
21 Correct 9 ms 9964 KB Output is correct
22 Correct 15 ms 10092 KB Output is correct
23 Correct 23 ms 9964 KB Output is correct
24 Correct 17 ms 9964 KB Output is correct
25 Correct 13 ms 10092 KB Output is correct
26 Correct 14 ms 10092 KB Output is correct
27 Correct 12 ms 10096 KB Output is correct
28 Correct 11 ms 9964 KB Output is correct
29 Correct 12 ms 9964 KB Output is correct
30 Correct 11 ms 9964 KB Output is correct
31 Execution timed out 3059 ms 42452 KB Time limit exceeded
32 Halted 0 ms 0 KB -