oj.uz

Submission #518997

# Submission time Handle Problem Language Result Execution time Memory
518997 2022-01-25T10:12:19 Z Keshi Unique Cities (JOI19_ho_t5) C++17
32 / 100
 935 ms 72620 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], prv[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;
}
int get(int id, int s, int e, int l, int r){
	if(r <= s || e <= l) return inf;
	if(l <= s && e <= r) return seg[id];
	int mid = (s + e) >> 1;
	seg[lc] += lz[id];
	lz[lc] += lz[id];
	seg[rc] += lz[id];
	lz[rc] += lz[id];
	lz[id] = 0;
	return min(get(lc, s, mid, l, r), get(rc, mid, e, l, r));
}

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]);
		}
		int pr = prv[c[v]];
		if(pr == 0 || get(1, 0, n, d[pr], d[pr] + 1) != 0){
			prv[c[v]] = v;
		}
		else{
			upd(1, 0, n, d[v], d[v] + 1, 1);
		}
		upd(1, 0, n, x, d[v], 1);
		solve(u);
		upd(1, 0, n, x, d[v], -1);
		if(prv[c[v]] == v){
			prv[c[v]] = pr;
		}
		else{
			upd(1, 0, n, d[v], d[v] + 1, -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++){
		cout << ans[i] << "\n";
	}
	
	return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9708 KB Output is correct
2 Incorrect 8 ms 9920 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 452 ms 22040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 601 ms 28616 KB Output is correct
2 Correct 895 ms 70080 KB Output is correct
3 Correct 87 ms 16716 KB Output is correct
4 Correct 845 ms 31744 KB Output is correct
5 Correct 935 ms 72620 KB Output is correct
6 Correct 844 ms 52492 KB Output is correct
7 Correct 724 ms 32120 KB Output is correct
8 Correct 787 ms 40416 KB Output is correct
9 Correct 748 ms 37556 KB Output is correct
10 Correct 730 ms 35288 KB Output is correct
11 Correct 611 ms 34144 KB Output is correct
12 Correct 877 ms 64740 KB Output is correct
13 Correct 745 ms 49596 KB Output is correct
14 Correct 898 ms 50088 KB Output is correct
15 Correct 625 ms 35396 KB Output is correct
16 Correct 861 ms 59212 KB Output is correct
17 Correct 839 ms 53032 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9708 KB Output is correct
2 Incorrect 8 ms 9920 KB Output isn't correct
3 Halted 0 ms 0 KB -