oj.uz

Submission #671181

# Submission time Handle Problem Language Result Execution time Memory
671181 2022-12-12T09:51:49 Z dozer Unique Cities (JOI19_ho_t5) C++14
32 / 100
 369 ms 43668 KB 
#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 200005 
 
 
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();
	}
	//for (auto i : s) cerr<<arr[i]<<sp;
	//cerr<<"->"<<res<<endl;
}


void add(int node)
{
	if (s.empty() || s.back() != node)
	{
		s.pb(node);
		cnt[arr[node]]++;
		if (cnt[arr[node]] == 1) res++;
	}
	//for (auto i : s) cerr<<arr[i]<<sp;
	//cerr<<"->"<<res<<endl;
}

void dfs(int node, int root, int d) 
{ 
	dist[node] = d; 
	dep[node] = d; 
	for (auto i : adj[node])  
	{ 
		if (i == root) continue;
		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[curr] > 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);
 	vector<int> ord;
 	if (top != 0) ord.pb(top), 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) 
		{
			ord.pb(curr);
			add(node);
			dfs2(curr, node);
		}
	} 
	del(dist[node]);
	ans[node] = max(ans[node], res); 
	//cout<<node<<" : ";
	////for (auto i : ord) cout<<i<<sp;
	////cout<<"||| ";
	//for (auto i : s) cout<<i<<sp;
	//cout<<endl;
} 
 


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; 

	dfs(root, 0, 1); 
	dfs2(root, 0); 
 	
	maks = {0, 0}; 
	for (int i = 1; i <= n; i++) maks = max(maks, {dist[i], i});
	for (int i = 1; i <= m; i++) cnt[i] = 0; 
	s.clear();
	res = 0;
	root = maks.nd; 
	dfs(root, 0, 1); 
	dfs2(root, 0); 
	for (int i = 1; i <= n; i++) 
		cout<<min(1, ans[i])<<endl; 

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

Compilation message

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

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 3 ms 5076 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 10716 KB Output is correct
2 Correct 165 ms 27220 KB Output is correct
3 Correct 29 ms 8404 KB Output is correct
4 Correct 272 ms 14888 KB Output is correct
5 Correct 369 ms 43668 KB Output is correct
6 Correct 334 ms 29100 KB Output is correct
7 Correct 252 ms 15220 KB Output is correct
8 Correct 276 ms 17804 KB Output is correct
9 Correct 284 ms 16876 KB Output is correct
10 Correct 272 ms 16816 KB Output is correct
11 Correct 131 ms 16868 KB Output is correct
12 Correct 347 ms 32800 KB Output is correct
13 Correct 295 ms 28736 KB Output is correct
14 Correct 321 ms 28112 KB Output is correct
15 Correct 123 ms 16888 KB Output is correct
16 Correct 308 ms 34364 KB Output is correct
17 Correct 343 ms 29344 KB Output is correct

Subtask #3
0 / 32.0

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

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 3 ms 5076 KB Output isn't correct
3 Halted 0 ms 0 KB -