oj.uz

Submission #518986

# Submission time Handle Problem Language Result Execution time Memory
518986 2022-01-25T09:59:39 Z Keshi Unique Cities (JOI19_ho_t5) C++17
64 / 100
 856 ms 69452 KB 
//In the name of God
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int maxn = 2e5 + 100;
const int mod = 1e9 + 7;
const int inf = 1e9;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()
#define lc (id << 1)
#define rc (lc | 1)

ll pw(ll a, ll b){
	ll c = 1;
	while(b){
		if(b & 1) c = c * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return c;
}

int n, m, c[maxn], d[maxn], mx, r1, r2, dd[maxn], ans[maxn];
vector<int> g[maxn];
bool vis[maxn];
int seg[maxn << 2], lz[maxn << 2], cnt[maxn << 2];

void bld(int id, int s, int e){
	seg[id] = lz[id] = 0;
	cnt[id] = e - s;
	if(e - s == 1) return;
	int mid = (s + e) >> 1;
	bld(lc, s, mid);
	bld(rc, mid, e);
	return;
}

void upd(int id, int s, int e, int l, int r, int x){
	if(r <= s || e <= l) return;
	if(l <= s && e <= r){
		seg[id] += x;
		lz[id] += x;
		return;
	}
	int mid = (s + e) >> 1;
	seg[lc] += lz[id];
	lz[lc] += lz[id];
	seg[rc] += lz[id];
	lz[rc] += lz[id];
	lz[id] = 0;
	upd(lc, s, mid, l, r, x);
	upd(rc, mid, e, l, r, x);
	seg[id] = min(seg[lc], seg[rc]);
	cnt[id] = 0;
	if(seg[id] == seg[lc]) cnt[id] += cnt[lc];
	if(seg[id] == seg[rc]) cnt[id] += cnt[rc];
	return;
}

void difs(int v){
	vis[v] = 1;
	if(d[v] > d[mx]) mx = v;
	for(int u : g[v]){
		if(vis[u]) continue;
		d[u] = d[v] + 1;
		difs(u);
	}
	return;
}
vector<int> gg[maxn];

void prep(int v, int p = -1){
	gg[v].clear();
	dd[v] = d[v];
	for(int u : g[v]){
		if(u == p) continue;
		d[u] = d[v] + 1;
		gg[v].pb(u);
		prep(u, v);
		dd[v] = max(dd[v], dd[u]);
	}
	return;
}

void solve(int v){
	upd(1, 0, n, d[v] - (dd[v] - d[v]), d[v], 1);
	ans[v] = max(ans[v], cnt[1] - (n - d[v]));
	upd(1, 0, n, d[v] - (dd[v] - d[v]), d[v], -1);
	vector<pll> vec;
	vec.pb(Mp(-d[v], v));
	for(int u : gg[v]){
		vec.pb(Mp(-dd[u], u));
	}
	sort(all(vec));
	for(int u : gg[v]){
		int x = d[v] - (-vec[0].F - d[v]);
		if(u == vec[0].S){
			x = d[v] - (-vec[1].F - d[v]);
		}
		upd(1, 0, n, x, d[v], 1);
		solve(u);
		upd(1, 0, n, x, d[v], -1);
	}
	return;
}

int main(){
	fast_io;

	cin >> n >> m;
	for(int i = 1; i < n; i++){
		int v, u;
		cin >> v >> u;
		g[v].pb(u);
		g[u].pb(v);
	}
	for(int i = 1; i <= n; i++){
		cin >> c[i];
	}
	d[1] = 0;
	difs(1);
	r1 = mx;
	fill(vis, vis + n + 10, 0);
	d[r1] = 0;
	difs(r1);
	r2 = mx;
	d[r1] = 0;
	prep(r1);
	bld(1, 0, n);
	solve(r1);
	d[r2] = 0;
	prep(r2);
	bld(1, 0, n);
	solve(r2);

	for(int i = 1; i <= n; i++){
		ans[i] = min(ans[i], m);
		cout << ans[i] << "\n";
	}
	
	return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Incorrect 9 ms 9932 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 20780 KB Output is correct
2 Correct 398 ms 43564 KB Output is correct
3 Correct 76 ms 15504 KB Output is correct
4 Correct 655 ms 32684 KB Output is correct
5 Correct 856 ms 69452 KB Output is correct
6 Correct 813 ms 51644 KB Output is correct
7 Correct 610 ms 33672 KB Output is correct
8 Correct 696 ms 36864 KB Output is correct
9 Correct 662 ms 35568 KB Output is correct
10 Correct 693 ms 35364 KB Output is correct
11 Correct 558 ms 37392 KB Output is correct
12 Correct 793 ms 56212 KB Output is correct
13 Correct 752 ms 51984 KB Output is correct
14 Correct 796 ms 50412 KB Output is correct
15 Correct 554 ms 37168 KB Output is correct
16 Correct 715 ms 57512 KB Output is correct
17 Correct 762 ms 52116 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 26844 KB Output is correct
2 Correct 792 ms 65096 KB Output is correct
3 Correct 88 ms 15684 KB Output is correct
4 Correct 662 ms 29760 KB Output is correct
5 Correct 840 ms 67408 KB Output is correct
6 Correct 772 ms 48968 KB Output is correct
7 Correct 679 ms 30176 KB Output is correct
8 Correct 731 ms 37768 KB Output is correct
9 Correct 664 ms 35216 KB Output is correct
10 Correct 731 ms 33044 KB Output is correct
11 Correct 572 ms 32268 KB Output is correct
12 Correct 809 ms 60236 KB Output is correct
13 Correct 743 ms 46396 KB Output is correct
14 Correct 786 ms 46764 KB Output is correct
15 Correct 603 ms 34280 KB Output is correct
16 Correct 732 ms 55076 KB Output is correct
17 Correct 700 ms 49440 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Incorrect 9 ms 9932 KB Output isn't correct
3 Halted 0 ms 0 KB -