Submission #518925

#	Time	Username	Problem	Language	Result	Execution time	Memory
518925		AmShZ	Unique Cities (JOI19_ho_t5)	C++11	100 / 100	1926 ms	199748 KiB

joi2019_ho_t5

//khodaya khodet komak kon
# include <bits/stdc++.h>

using namespace std;

typedef long long                                        ll;
typedef long double                                      ld;
typedef pair <int, int>                                  pii;
typedef pair <pii, int>                                  ppi;
typedef pair <int, pii>                                  pip;
typedef pair <pii, pii>                                  ppp;
typedef pair <ll, ll>                                    pll;

# define A                                               first
# define B                                               second
# define endl                                            '\n'
# define sep                                             ' '
# define all(x)                                          x.begin(), x.end()
# define kill(x)                                         return cout << x << endl, 0
# define SZ(x)                                           int(x.size())
# define lc                                              id << 1
# define rc                                              id << 1 | 1
# define fast_io                                         ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);

ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}

const int xn = 2e5 + 10;
const int xm = 10 + 10;
const int sq = 320;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const ld eps = 1e-15;
const int mod = 998244353;
const int base = 257;

int n, m, c[xn], dmx[2][xn], par[xm][xn * 3], col[xn * 3];
int dist[xm][xn * 3], P[xn], cnt[xn], s, ans[xn];
vector <int> adj[xn], g[xn * 3];
vector <pii> G[xn * 3];

void DFS1(int v, int p = - 1){
	for (int u : adj[v])
		if (u != p)
			DFS1(u, v), dmx[0][v] = max(dmx[0][v], dmx[0][u] + 1);
}
void DFS2(int v, int p = - 1){
	vector <int> vec;
	vec.push_back(dmx[1][v] + 1);
	for (int u : adj[v])
		if (u != p)
			vec.push_back(dmx[0][u] + 1);
	sort(all(vec));
	for (int u : adj[v]){
		if (u == p)
			continue;
		if (dmx[0][u] + 1 == vec.back())
			dmx[1][u] = vec[SZ(vec) - 2];
		else
			dmx[1][u] = vec.back();
		DFS2(u, v);
	}
}
void add_edge(int v, int u, int w){
	G[u].push_back({v, w});
	//cout << v << " -> " << u << " : " << w << endl;
	//par[0][v] = u;
}
void DFS3(int v, int p = - 1){
	vector <pii> vec;
	vec.push_back({0, 0});
	vec.push_back({0, 0});
	P[v] = p;
	for (int u : adj[v])
		if (u != p)
			vec.push_back({dmx[0][u] + 1, u + n});
	sort(all(vec));
	add_edge(v + n, vec.back().B, vec[SZ(vec) - 2].A);
	vec.push_back({dmx[1][v] + 1, v + n + n});
	sort(all(vec));
	add_edge(v, vec.back().B, vec[SZ(vec) - 2].A);
	for (int u : adj[v]){
		if (u == p)
			continue;
		if (u + n == vec.back().B)
			add_edge(u + n + n, vec[SZ(vec) - 2].B, vec[SZ(vec) - 3].A);
		else if (u + n == vec[SZ(vec) - 2].B)
			add_edge(u + n + n, vec[SZ(vec) - 1].B, vec[SZ(vec) - 3].A);
		else
			add_edge(u + n + n, vec[SZ(vec) - 1].B, vec[SZ(vec) - 2].A);
	}
	for (int u : adj[v])
		if (u != p)
			DFS3(u, v);
}
void DFS4(int v, int w = - 1){
	for (int i = 1; i < xm; ++ i){
		par[i][v] = par[i - 1][par[i - 1][v]];
		dist[i][v] = dist[i - 1][v] + dist[i - 1][par[i - 1][v]];
		if (!v)
			dist[i][v] = inf;
	}
	int res = v, d = 0;
	for (int i = xm - 1; 0 <= i; -- i){
		if (w < d + dist[i][res])
			continue;
		d += dist[i][res];
		res = par[i][res];
	}
	dist[0][v] = d + dist[0][res];
	par[0][v] = par[0][res];
	if (v)
		g[par[0][v]].push_back(v);
	for (int i = 1; i < xm; ++ i){
		par[i][v] = par[i - 1][par[i - 1][v]];
		dist[i][v] = dist[i - 1][v] + dist[i - 1][par[i - 1][v]];
	}
	if (!v)
		for (int i = 0; i < xm; ++ i)
			par[i][0] = 0, dist[0][0] = inf;
	for (pii u : G[v]){
		par[0][u.A] = v;
		dist[0][u.A] = 1;
		if (v == 0)
			dist[0][u.A] = inf;
		DFS4(u.A, u.B);
	}
}
void add(int x, int val){
	s -= (0 < cnt[x]);
	cnt[x] += val;
	s += (0 < cnt[x]);
}
void DFS5(int v){
	if (v <= n)
		ans[v] = s;
	else if (v <= n + n)
		col[v] = c[v - n];
	else
		col[v] = c[P[v - n - n]];
	add(col[v], 1);
	for (int u : g[v])
		DFS5(u);
	add(col[v], - 1);
}

int main(){
	//fast_io;

	cin >> n >> m;
	for (int i = 1; i < n; ++ i){
		int v, u;
		cin >> v >> u;
		adj[v].push_back(u);
		adj[u].push_back(v);
	}
	for (int i = 1; i <= n; ++ i)
		cin >> c[i];
	dmx[1][1] = - 1;
	add_edge(1 + n + n, 0, 0);
	DFS1(1);
	DFS2(1);
	DFS3(1);
	DFS4(0);
	DFS5(0);
	for (int i = 1; i <= n; ++ i)
		cout << ans[i] - 1 << endl;

	return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 32 / 32
• Subtask 3: 32 / 32
• Subtask 4: 32 / 32