oj.uz

Submission #518984

# Submission time Handle Problem Language Result Execution time Memory
518984 2022-01-25T09:58:27 Z Keshi Unique Cities (JOI19_ho_t5) C++17
32 / 100
 951 ms 71216 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++){
		cout << ans[i] << "\n";
	}
	
	return 0;
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 320 ms 22432 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 511 ms 29760 KB Output is correct
2 Correct 834 ms 68732 KB Output is correct
3 Correct 120 ms 16320 KB Output is correct
4 Correct 630 ms 33652 KB Output is correct
5 Correct 826 ms 71216 KB Output is correct
6 Correct 824 ms 52820 KB Output is correct
7 Correct 682 ms 33948 KB Output is correct
8 Correct 775 ms 41632 KB Output is correct
9 Correct 829 ms 38924 KB Output is correct
10 Correct 810 ms 36880 KB Output is correct
11 Correct 708 ms 36136 KB Output is correct
12 Correct 951 ms 64076 KB Output is correct
13 Correct 748 ms 50056 KB Output is correct
14 Correct 762 ms 50612 KB Output is correct
15 Correct 596 ms 38080 KB Output is correct
16 Correct 774 ms 58904 KB Output is correct
17 Correct 693 ms 53204 KB Output is correct

Subtask #4
0 / 32.0

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