oj.uz

Submission #113993

# Submission time Handle Problem Language Result Execution time Memory
113993 2019-05-29T12:58:00 Z RockyB Unique Cities (JOI19_ho_t5) C++17
4 / 100
 2000 ms 18552 KB 
/// In The Name Of God

#include <bits/stdc++.h>

#define f first
#define s second

#define pb push_back
#define pp pop_back
#define mp make_pair

#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()

#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, l, r) for (int i = (l); i >= (r); i--)

#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

#define nl '\n'
#define ioi exit(0);

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int N = (int)5e5 + 7;
const int inf = (int)1e9 + 7;
const int mod = (int)1e9 + 7;
const ll linf = (ll)1e18 + 7;

const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};

using namespace std;

int n, m;
int c[N];
vector <int> g[N];

int A, B;
int mx;
void dfs(int v, int p, int dis, int &D) {
	if (dis > mx) {
		mx = dis;
		D = v;
	}
	for (auto to : g[v]) {
		if (to != p) {
			dfs(to, v, dis + 1, D);
		}
	}
}

int dp[N];
set <int> col;
void pre(int v, int p = -1) {
	dp[v] = 0;
	for (auto to : g[v]) {
		if (to != p) {
			pre(to, v);
			dp[v] = max(dp[v], dp[to] + 1);
		}
	}
}
void go(int v, int p = -1, int ost = 0) {
	if (ost < 0) col.insert(c[v]);
	pair <int, int> mx = {-1, -1};
	for (auto to : g[v]) {
		if (to != p) {
			if (dp[to] >= mx.f) {
				mx.s = mx.f;
				mx.f = dp[to];
			}
			else if (dp[to] > mx.s) {
				mx.s = dp[to];
			}
		}
	}
	//if (mx.f == mx.s) return;
	for (auto to : g[v]) {
		if (to != p) {
			if (dp[to] == mx.f) go(to, v, max(ost - 1, mx.s));
		}
	}
}
void solve(int v) {
	pre(v);
	col.clear();
	go(v);
	cout << sz(col) << nl;
}
int main() {
	#ifdef IOI2018
		freopen ("in.txt", "r", stdin);
	#endif
	Kazakhstan
	// --- reading input
	cin >> n >> m;
	rep(i, 2, n) {
		int v, u;
		cin >> v >> u;
		g[v].pb(u);
		g[u].pb(v);
	}
	rep(i, 1, n) cin >> c[i];
	// --- finding diameter
	dfs(1, 0, 0, A);
	mx = 0;
	dfs(A, 0, 0, B);
	// --- solving part
	rep(i, 1, n) {
		solve(i);
	}
	ioi
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12160 KB Output is correct
2 Correct 75 ms 12160 KB Output is correct
3 Correct 86 ms 12408 KB Output is correct
4 Correct 125 ms 12320 KB Output is correct
5 Correct 88 ms 12280 KB Output is correct
6 Correct 220 ms 12380 KB Output is correct
7 Correct 143 ms 12412 KB Output is correct
8 Correct 85 ms 12160 KB Output is correct
9 Correct 107 ms 12160 KB Output is correct
10 Correct 103 ms 12228 KB Output is correct
11 Correct 107 ms 12328 KB Output is correct
12 Correct 53 ms 12160 KB Output is correct
13 Correct 211 ms 12488 KB Output is correct
14 Correct 124 ms 12160 KB Output is correct
15 Correct 142 ms 12452 KB Output is correct
16 Correct 67 ms 12220 KB Output is correct
17 Correct 125 ms 12380 KB Output is correct
18 Correct 121 ms 12408 KB Output is correct
19 Correct 89 ms 12160 KB Output is correct
20 Correct 409 ms 12536 KB Output is correct
21 Correct 179 ms 12288 KB Output is correct
22 Correct 85 ms 12212 KB Output is correct
23 Correct 102 ms 12160 KB Output is correct
24 Correct 129 ms 12348 KB Output is correct
25 Correct 94 ms 12160 KB Output is correct
26 Correct 50 ms 12160 KB Output is correct
27 Correct 280 ms 12288 KB Output is correct
28 Correct 200 ms 12288 KB Output is correct
29 Correct 142 ms 12288 KB Output is correct
30 Correct 65 ms 12160 KB Output is correct
31 Correct 184 ms 12408 KB Output is correct
32 Correct 151 ms 12288 KB Output is correct

Subtask #2
0 / 32.0

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

Subtask #3
0 / 32.0

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

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12160 KB Output is correct
2 Correct 75 ms 12160 KB Output is correct
3 Correct 86 ms 12408 KB Output is correct
4 Correct 125 ms 12320 KB Output is correct
5 Correct 88 ms 12280 KB Output is correct
6 Correct 220 ms 12380 KB Output is correct
7 Correct 143 ms 12412 KB Output is correct
8 Correct 85 ms 12160 KB Output is correct
9 Correct 107 ms 12160 KB Output is correct
10 Correct 103 ms 12228 KB Output is correct
11 Correct 107 ms 12328 KB Output is correct
12 Correct 53 ms 12160 KB Output is correct
13 Correct 211 ms 12488 KB Output is correct
14 Correct 124 ms 12160 KB Output is correct
15 Correct 142 ms 12452 KB Output is correct
16 Correct 67 ms 12220 KB Output is correct
17 Correct 125 ms 12380 KB Output is correct
18 Correct 121 ms 12408 KB Output is correct
19 Correct 89 ms 12160 KB Output is correct
20 Correct 409 ms 12536 KB Output is correct
21 Correct 179 ms 12288 KB Output is correct
22 Correct 85 ms 12212 KB Output is correct
23 Correct 102 ms 12160 KB Output is correct
24 Correct 129 ms 12348 KB Output is correct
25 Correct 94 ms 12160 KB Output is correct
26 Correct 50 ms 12160 KB Output is correct
27 Correct 280 ms 12288 KB Output is correct
28 Correct 200 ms 12288 KB Output is correct
29 Correct 142 ms 12288 KB Output is correct
30 Correct 65 ms 12160 KB Output is correct
31 Correct 184 ms 12408 KB Output is correct
32 Correct 151 ms 12288 KB Output is correct
33 Execution timed out 2071 ms 16672 KB Time limit exceeded
34 Halted 0 ms 0 KB -