oj.uz

답안 #381665

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
381665 2021-03-25T13:55:19 Z Return_0 수도 (JOI20_capital_city) C++17
11 / 100
 3000 ms 35696 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

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9836 KB Output is correct
2 Correct 6 ms 9836 KB Output is correct
3 Correct 7 ms 9852 KB Output is correct
4 Correct 8 ms 9856 KB Output is correct
5 Correct 7 ms 9848 KB Output is correct
6 Correct 6 ms 9836 KB Output is correct
7 Correct 6 ms 9836 KB Output is correct
8 Correct 6 ms 9836 KB Output is correct
9 Correct 7 ms 9836 KB Output is correct
10 Correct 6 ms 9836 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9836 KB Output is correct
2 Correct 6 ms 9836 KB Output is correct
3 Correct 7 ms 9852 KB Output is correct
4 Correct 8 ms 9856 KB Output is correct
5 Correct 7 ms 9848 KB Output is correct
6 Correct 6 ms 9836 KB Output is correct
7 Correct 6 ms 9836 KB Output is correct
8 Correct 6 ms 9836 KB Output is correct
9 Correct 7 ms 9836 KB Output is correct
10 Correct 6 ms 9836 KB Output is correct
11 Correct 11 ms 9964 KB Output is correct
12 Correct 11 ms 9964 KB Output is correct
13 Correct 11 ms 9964 KB Output is correct
14 Correct 13 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 9 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 16 ms 9984 KB Output is correct
25 Correct 12 ms 9964 KB Output is correct
26 Correct 12 ms 9964 KB Output is correct
27 Correct 12 ms 9964 KB Output is correct
28 Correct 10 ms 9964 KB Output is correct
29 Correct 12 ms 9964 KB Output is correct
30 Correct 10 ms 9964 KB Output is correct

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3043 ms 35696 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9836 KB Output is correct
2 Correct 6 ms 9836 KB Output is correct
3 Correct 7 ms 9852 KB Output is correct
4 Correct 8 ms 9856 KB Output is correct
5 Correct 7 ms 9848 KB Output is correct
6 Correct 6 ms 9836 KB Output is correct
7 Correct 6 ms 9836 KB Output is correct
8 Correct 6 ms 9836 KB Output is correct
9 Correct 7 ms 9836 KB Output is correct
10 Correct 6 ms 9836 KB Output is correct
11 Correct 11 ms 9964 KB Output is correct
12 Correct 11 ms 9964 KB Output is correct
13 Correct 11 ms 9964 KB Output is correct
14 Correct 13 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 9 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 16 ms 9984 KB Output is correct
25 Correct 12 ms 9964 KB Output is correct
26 Correct 12 ms 9964 KB Output is correct
27 Correct 12 ms 9964 KB Output is correct
28 Correct 10 ms 9964 KB Output is correct
29 Correct 12 ms 9964 KB Output is correct
30 Correct 10 ms 9964 KB Output is correct
31 Execution timed out 3043 ms 35696 KB Time limit exceeded
32 Halted 0 ms 0 KB -