oj.uz

Submission #671178

# Submission time Handle Problem Language Result Execution time Memory
671178 2022-12-12T09:34:14 Z dozer Unique Cities (JOI19_ho_t5) C++14
32 / 100
 390 ms 47476 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();
	}
}


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) 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; 
	//cerr<<root<<endl; 
	dfs(root, 0, 1); 

	dfs2(root, 0); 
	//for (int i = 1; i <= n; i++) 
	//	cout<<ans[i]<<sp; 
	//cout<<endl; 
 	s.clear();
 	res = 0;
	maks = {0, 0}; 
	for (int i = 1; i <= n; i++) maks = max(maks, {dist[i], i}), cnt[i] = 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:57:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for (int i = 0; i < adj[node].size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~~~
joi2019_ho_t5.cpp:79:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  for (int i = 0; i < adj[node].size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 4 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 124 ms 11724 KB Output is correct
2 Correct 176 ms 29308 KB Output is correct
3 Correct 27 ms 8904 KB Output is correct
4 Correct 289 ms 18600 KB Output is correct
5 Correct 390 ms 47476 KB Output is correct
6 Correct 371 ms 32816 KB Output is correct
7 Correct 267 ms 18808 KB Output is correct
8 Correct 308 ms 21548 KB Output is correct
9 Correct 293 ms 20472 KB Output is correct
10 Correct 299 ms 20416 KB Output is correct
11 Correct 152 ms 20620 KB Output is correct
12 Correct 346 ms 36340 KB Output is correct
13 Correct 309 ms 32448 KB Output is correct
14 Correct 314 ms 31832 KB Output is correct
15 Correct 152 ms 20696 KB Output is correct
16 Correct 315 ms 38048 KB Output is correct
17 Correct 314 ms 33088 KB Output is correct

Subtask #3
0 / 32.0

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

Subtask #4
0 / 32.0

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