oj.uz

Submission #572832

# Submission time Handle Problem Language Result Execution time Memory
572832 2022-06-05T11:05:51 Z Arvin Meetings 2 (JOI21_meetings2) C++17
0 / 100
 6 ms 5076 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int maxN = 2e5 + 5;
const int logN = log2(maxN)+1;

vector<int> adj[maxN];
int parent[logN][maxN], sz[maxN], depth[maxN];
int c[maxN];

void dfs(int curNode, int prvNode, int d = 1){
	parent[0][curNode] = prvNode;
	for(int x=1;x<logN;x++){
		parent[x][curNode] = parent[x-1][parent[x-1][curNode]];
	}
	sz[curNode] = 1;
	c[curNode] = 0;
	depth[curNode] = d;
	for(auto nxt : adj[curNode]){
		if(nxt != prvNode){
			dfs(nxt, curNode, d+1);
		}
	}
}

void dfs2(int curNode, int prvNode){
	for(auto nxt : adj[curNode]){
		if(nxt != prvNode){
			dfs2(nxt, curNode);
			c[curNode] += (c[nxt] != 0);
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	
	int n;
	cin >> n;
	
	for(int x=0;x<n-1;x++){
		int a, b;
		cin >> a >> b;
		
		a--; b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	
	dfs(0, 0);
	
	pair<int, int> mx = {-1, -1};
	int d[n];
	for(int x=0;x<n;x++){
		mx = max(mx, {depth[x], x});
		d[x] = min(mx.first-depth[x]+1, depth[x]);
	}
	
	dfs(mx.second, mx.second);
	
	for(int x=0;x<n;x++){
		mx = max(mx, {depth[x], x});
	}
	
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	multiset<int> st;
	int cnt[n];
	fill(cnt, cnt+n, 0);
	fill(c, c+n, 0);
	
	for(int x=0;x<n;x++){
		if(adj[x].size() == 1){
			pq.push({1, x});
			c[x] = 1;
			sz[x] = 1;
			cnt[x] = 0;
//			cout << x << " = " << d[x] << " " << depth[x] << " " << mx.first << "\n";
			d[x] = min(d[x], min(mx.first-depth[x]+1, depth[x]));
			st.insert(d[x]);
		}
	}
	
	dfs2(mx.second, mx.second);
	
	for(int x=0;x<n;x++){
		if(depth[x] != 1){
			c[x]++;
		}
	}
	
	for(int x=1;x<=n;x++){
		if(x&1){
			cout << "1\n";
		} else {
			while(!pq.empty() && pq.top().first < x/2){
				int curNode = pq.top().second;
				st.erase(st.find(d[curNode]));
				pq.pop();
				
//				cout << "- " << curNode << " " << sz[curNode] << " " << d[curNode] << "\n";
				int par = -1;
				for(auto nxt : adj[curNode]){
//					cout << nxt << " = " << cnt[nxt] << " " << c[nxt] << "\n";
					if(cnt[nxt]+1 < adj[nxt].size()){
						par = nxt;
						break;
					}
				}
				
				if(par == -1) continue;
				
				cnt[par]++;
				sz[par] += sz[curNode];
				if(cnt[par]+1 == adj[par].size()){
//					cout << "+ " << par << " " << sz[par] << " " << d[curNode]+1 << "\n";
					pq.push({sz[par], par});
					d[par] = d[curNode]+1;
					st.insert(d[par]);
				}
			}
			
			int mn1 = -1, mn2 = -1;
			for(auto val : st){
//				cout << " = " << val << "\n";
				if(mn1 == -1){
					mn1 = val;
				} else if(mn2 == -1){
					mn2 = val;
				} else {
					break;
				}
			}
			
			assert(mn1 != -1);
			if(mn2 != -1) cout << mx.first-mn1-mn2+2 << "\n";
			else cout << "1\n";
		}
	}
//	cout << diameter << " --\n";
    return 0;
}

Compilation message

meetings2.cpp: In function 'int main()':
meetings2.cpp:109:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |      if(cnt[nxt]+1 < adj[nxt].size()){
      |         ~~~~~~~~~~~^~~~~~~~~~~~~~~~~
meetings2.cpp:119:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |     if(cnt[par]+1 == adj[par].size()){
      |        ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 2 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 5 ms 5076 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 2 ms 5076 KB Output is correct
12 Correct 3 ms 5036 KB Output is correct
13 Correct 3 ms 5028 KB Output is correct
14 Correct 6 ms 5076 KB Output is correct
15 Correct 3 ms 5076 KB Output is correct
16 Correct 3 ms 5076 KB Output is correct
17 Correct 3 ms 5028 KB Output is correct
18 Correct 4 ms 5020 KB Output is correct
19 Incorrect 3 ms 5076 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 2 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 5 ms 5076 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 2 ms 5076 KB Output is correct
12 Correct 3 ms 5036 KB Output is correct
13 Correct 3 ms 5028 KB Output is correct
14 Correct 6 ms 5076 KB Output is correct
15 Correct 3 ms 5076 KB Output is correct
16 Correct 3 ms 5076 KB Output is correct
17 Correct 3 ms 5028 KB Output is correct
18 Correct 4 ms 5020 KB Output is correct
19 Incorrect 3 ms 5076 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 2 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 5 ms 5076 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 2 ms 5076 KB Output is correct
12 Correct 3 ms 5036 KB Output is correct
13 Correct 3 ms 5028 KB Output is correct
14 Correct 6 ms 5076 KB Output is correct
15 Correct 3 ms 5076 KB Output is correct
16 Correct 3 ms 5076 KB Output is correct
17 Correct 3 ms 5028 KB Output is correct
18 Correct 4 ms 5020 KB Output is correct
19 Incorrect 3 ms 5076 KB Output isn't correct
20 Halted 0 ms 0 KB -