Submission #671150

#	Time	Username	Problem	Language	Result	Execution time	Memory
671150		dozer	Unique Cities (JOI19_ho_t5)	C++14	0 / 100	89 ms	21060 KiB

joi2019_ho_t5

#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w",  stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0) 
#define pb push_back 
#define st first 
#define nd second 
#define sp " " 
#define endl "\n" 
#define pii pair<int, int> 
#define N 100005 
 
 
const int modulo = 1e9 + 7; 
int dist[N], ans[N], dep[N], arr[N], cnt[N], res; 
vector<int> adj[N]; 
vector<int> s;

void del(int x)
{
	while(!s.empty() && dist[s.back()] >= x)
	{
		int curr = s.back();
		cnt[arr[curr]]--;
		if (cnt[arr[curr]] == 0) res--;
		s.pop_back();
	}
}


void add(int node)
{
	if (s.empty() || s.back() != node)
	{
		s.pb(node);
		cnt[arr[node]]++;
		if (cnt[arr[node]] == 1) res++;
	}
}

void dfs(int node, int root, int d) 
{ 
	dist[node] = d; 
	dep[node] = d; 
	for (auto i : adj[node])  
	{ 
		if (i != root) dfs(i, node, d + 1); 
		dep[node] = max(dep[node], dep[i]); 
	} 
} 
 
 
void dfs2(int node, int root) 
{ 
	pair<pii, pii> maks = {{0, 0}, {0, 0}};
	for (int i = 0; i < adj[node].size(); i++) 
	{ 
		int curr = adj[node][i];
		if (curr == root) continue;
		if (dep[node] > maks.st.st)
		{
			maks.nd = maks.st;
			maks.st = {dep[curr], curr};
		}
		else maks.nd = max(maks.nd, {dep[curr], curr});
	} 
	
 	int diff = maks.nd.st - dist[node];
 	int to = max(0, dist[node] - diff);
 	del(to);
 	int top = maks.st.nd;
 	add(node);
 	if (top != 0) dfs2(top, node);
 	diff = maks.st.st - dist[node];
 	to = max(0, dist[node] - diff);
 	del(to);
	for (int i = 0; i < adj[node].size(); i++) 
	{
		int curr = adj[node][i]; 
		if (curr != root && curr != top) 
		{
			add(node);
			dfs2(curr, node);
		}
	} 
	del(dist[node]);
	ans[node] = max(ans[node], res); 
} 
 


int32_t main() 
{ 
	fastio(); 
 
	int n, m; 
	cin>>n>>m; 
	for (int i = 1; i < n; i++) 
	{ 
		int u, v; 
		cin>>u>>v; 
		adj[u].pb(v); 
		adj[v].pb(u); 
	} 
 
	for (int i = 1; i <= n; i++) 
		cin>>arr[i]; 
 
	dfs(1, 0, 1); 
	 
	pii maks = {0, 0}; 
	for (int i = 1; i <= n; i++) maks = max(maks, {dist[i], i}); 
	int root = maks.nd; 
	cerr<<root<<endl; 
	dfs(root, 0, 1); 

	dfs2(root, 0); 
	//for (int i = 1; i <= n; i++) 
	//	cout<<ans[i]<<sp; 
	//cout<<endl; 
 
	maks = {0, 0}; 
	for (int i = 1; i <= n; i++) maks = max(maks, {dist[i], i});  
	root = maks.nd; 
	dfs(root, 0, 1); 
	dfs2(root, 0); 
	for (int i = 1; i <= n; i++) 
		cout<<ans[i]<<endl; 

	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n"; 
}

Compilation message (stderr)

joi2019_ho_t5.cpp: In function 'void dfs2(int, int)':
joi2019_ho_t5.cpp:56:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for (int i = 0; i < adj[node].size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:77:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  for (int i = 0; i < adj[node].size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~~~

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