Submission #157478

#	Time	Username	Problem	Language	Result	Execution time	Memory
157478		ZwariowanyMarcin	Unique Cities (JOI19_ho_t5)	C++14	100 / 100	595 ms	52472 KiB

joi2019_ho_t5

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define mp make_pair
#define pb push_back
#define ld long double
#define ss(x) (int) x.size()
#define FOR(i, j, n) for(int i = j; i <= n; ++i)
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl;
#define ios cin.tie(0); ios_base::sync_with_stdio(0)
 
 
using namespace std;	

const int nax = 2e5 + 111;

int dif, n, a, b, m;
int ile[nax];
int h[nax];
int col[nax];
deque <int> q;
pair<int, int> maks;
int dp[nax];

vector <int> v[nax];
int ans[nax];

void add(int u) {
	dif += ile[col[u]] == 0;
	ile[col[u]] += 1;
	q.push_back(u);
}

void del() {
	int u = q.back();
	dif -= ile[col[u]] == 1;
	ile[col[u]] -= 1;
	q.pop_back();
}

void dfs(int u, int p) {
	h[u] = h[p] + 1;
	maks = max(maks, mp(h[u], u));
	dp[u] = 0;
	for(auto it : v[u]) {
		if(it != p) {
			dfs(it, u);
			dp[u] = max(dp[u], dp[it]);
		}
	}
	dp[u] += 1;
}

void solve(int u, int p) {
	vector <pair<int, int>> som;
	for(auto it : v[u])
		if(it != p) {
			som.pb(mp(dp[it], it));
		}
	sort(som.begin(), som.end());
	reverse(som.begin(), som.end());
	
	int maxi = (ss(som) > 1 ? som[1].fi : 0);
	for(auto it : som) {
		while(!q.empty() && h[u] - h[q.back()] <= maxi)
			del();
		add(u);
		solve(it.se, u);
		while(!q.empty() && h[q.back()] >= h[u])
			del();
		maxi = som[0].fi;
	}
	while(!q.empty() && h[u] - h[q.back()] <= maxi)
			del();
	ans[u] = max(ans[u], dif);
}
		

int main() {
	scanf("%d %d", &n, &m);
	FOR(i, 1, n - 1) {
		scanf("%d %d", &a, &b);
		v[a].pb(b);
		v[b].pb(a);
	}
	FOR(i, 1, n)
		scanf("%d", &col[i]);
	dfs(1, 0);
	
	int A = maks.se;
	
	fill(h + 1, h + n + 1, 0);
	maks = mp(-1, -1);
	dfs(A, 0);
	solve(A, 0);
	
	int B = maks.se;
	
	fill(h + 1, h + n + 1, 0);
	dfs(B, 0);
	solve(B, 0);
	
	FOR(i, 1, n)	
		printf("%d\n", ans[i]);
	
	
	
	
	
	return 0;
}

Compilation message (stderr)

joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:84:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:86:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &col[i]);
   ~~~~~^~~~~~~~~~~~~~~

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