oj.uz

Submission #671179

# Submission time Handle Problem Language Result Execution time Memory
671179 2022-12-12T09:38:51 Z dozer Unique Cities (JOI19_ho_t5) C++14
32 / 100
 410 ms 49140 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], (int)s.size()); 
	//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<<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 2 ms 4948 KB Output is correct
2 Incorrect 4 ms 5140 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

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

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 13520 KB Output is correct
2 Correct 398 ms 47276 KB Output is correct
3 Correct 34 ms 9588 KB Output is correct
4 Correct 294 ms 19496 KB Output is correct
5 Correct 410 ms 49140 KB Output is correct
6 Correct 367 ms 33920 KB Output is correct
7 Correct 271 ms 19668 KB Output is correct
8 Correct 309 ms 25328 KB Output is correct
9 Correct 319 ms 23300 KB Output is correct
10 Correct 308 ms 21668 KB Output is correct
11 Correct 223 ms 20280 KB Output is correct
12 Correct 372 ms 43104 KB Output is correct
13 Correct 329 ms 31952 KB Output is correct
14 Correct 382 ms 32344 KB Output is correct
15 Correct 151 ms 21552 KB Output is correct
16 Correct 322 ms 39516 KB Output is correct
17 Correct 329 ms 34376 KB Output is correct

Subtask #4
0 / 32.0

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