Submission #544618

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
544618	2022-04-02T13:44:23 Z	ivan_tudor	Meetings 2 (JOI21_meetings2)	C++14	100 / 100	532 ms	72404 KB

meetings2

#include<bits/stdc++.h>
using namespace std;
const int N = 200005;
vector<int> gr[N];
set<int> auxgr[N];
struct helpertime{
	int nod, dad;
	int sz;
};
int sz[N];
priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> leafs;
vector<helpertime> ht;
int ans[N];


int par[20][N];
int in[N], out[N];
int h[N];
void dfs_prec(int nod, int dad, int &cnt){
	h[nod] = h[dad] + 1;
	in[nod] = ++cnt;
	par[0][nod] = dad;
	for(int i = 1; i < 20; i ++)
		par[i][nod] = par[i - 1][par[i - 1][nod]];
	for(auto x:gr[nod]){
		if(x == dad)
			continue;
		dfs_prec(x, nod, cnt);
	}
	out[nod] = cnt;
}
bool is_dad(int dad, int son){
	if(in[dad] <= in[son] && out[son] <= out[dad])
		return true;
	return false;
}
int get_dist(int a, int b){
	if(h[a] > h[b])
		swap(a, b);
	if(is_dad(a, b))
		return h[b] - h[a] + 1;
	int lca = a;
	for(int p2 = 19; p2>=0; p2--){
		int up = par[p2][lca];
		if(up != 0 && is_dad(up, b) == false)
			lca = up;
	}
	lca = par[0][lca];
	return h[a] - h[lca] + 1 + h[b] - h[lca];
}

int main()
{
  //freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  int n;
  cin>>n;
  for(int i = 1; i<n; i++){
		int x, y;
		cin>>x>>y;
		gr[x].push_back(y);
		gr[y].push_back(x);

		auxgr[x].insert(y);
		auxgr[y].insert(x);
  }
	for(int i = 1; i<=n; i++){
		sz[i] = 1;
	}
	for(int i = 1; i<=n; i++){
		if(auxgr[i].size() == 1){
			leafs.push({sz[i], i});
		}
	}

	for(int t = 2; t <= n/2 + 1; t++){
		while(leafs.size() && leafs.top().first < t){
			int nod = leafs.top().second;
			leafs.pop();
			if(auxgr[nod].size()){
				assert(auxgr[nod].size() == 1);
				int vec = *auxgr[nod].begin();
				auxgr[nod].erase(vec);
				auxgr[vec].erase(nod);
				sz[vec] += sz[nod];
				ht.push_back({nod, vec, sz[nod]});
				if(auxgr[vec].size() == 1){
					leafs.push({sz[vec], vec});
				}
			}
		}
	}
	int cnt = 0;
	dfs_prec(1, 0, cnt);

	int root = 0;
	for(int i = 1; i<=n; i++)
		if(sz[i] == n)
			root = i;
	int diama = root, diamb = root;
	int dst = 1;
	for(int t = n/2; t>=1; t--){
		while(ht.size() && ht.back().sz >= t){
			int newnod = ht.back().nod;
			int dstna = get_dist(diama, newnod);
			int dstnb = get_dist(diamb, newnod);
			if(dstna > dst && dstna >= dstnb){
				dst = dstna;
				diamb = newnod;
			}
			else if(dstnb > dst && dstnb >= dstna){
				dst = dstnb;
				diama = newnod;
			}
			ht.pop_back();
		}
		ans[2*t] = dst;
		ans[2*t + 1] = 1;
	}
	ans[1] = 1;
	for(int i = 1; i<=n; i++){
		cout<<ans[i]<<"\n";
	}
  return 0;
}

Subtask #1
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	14548 KB	Output is correct
2	Correct	7 ms	14548 KB	Output is correct
3	Correct	7 ms	14548 KB	Output is correct
4	Correct	9 ms	14548 KB	Output is correct
5	Correct	8 ms	14548 KB	Output is correct
6	Correct	8 ms	14548 KB	Output is correct
7	Correct	9 ms	14544 KB	Output is correct
8	Correct	8 ms	14548 KB	Output is correct
9	Correct	7 ms	14548 KB	Output is correct
10	Correct	8 ms	14548 KB	Output is correct
11	Correct	7 ms	14556 KB	Output is correct
12	Correct	7 ms	14552 KB	Output is correct
13	Correct	7 ms	14548 KB	Output is correct
14	Correct	7 ms	14548 KB	Output is correct
15	Correct	7 ms	14508 KB	Output is correct
16	Correct	7 ms	14536 KB	Output is correct
17	Correct	7 ms	14552 KB	Output is correct
18	Correct	7 ms	14548 KB	Output is correct
19	Correct	7 ms	14552 KB	Output is correct
20	Correct	7 ms	14556 KB	Output is correct
21	Correct	8 ms	14556 KB	Output is correct

Subtask #2
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	14548 KB	Output is correct
2	Correct	7 ms	14548 KB	Output is correct
3	Correct	7 ms	14548 KB	Output is correct
4	Correct	9 ms	14548 KB	Output is correct
5	Correct	8 ms	14548 KB	Output is correct
6	Correct	8 ms	14548 KB	Output is correct
7	Correct	9 ms	14544 KB	Output is correct
8	Correct	8 ms	14548 KB	Output is correct
9	Correct	7 ms	14548 KB	Output is correct
10	Correct	8 ms	14548 KB	Output is correct
11	Correct	7 ms	14556 KB	Output is correct
12	Correct	7 ms	14552 KB	Output is correct
13	Correct	7 ms	14548 KB	Output is correct
14	Correct	7 ms	14548 KB	Output is correct
15	Correct	7 ms	14508 KB	Output is correct
16	Correct	7 ms	14536 KB	Output is correct
17	Correct	7 ms	14552 KB	Output is correct
18	Correct	7 ms	14548 KB	Output is correct
19	Correct	7 ms	14552 KB	Output is correct
20	Correct	7 ms	14556 KB	Output is correct
21	Correct	8 ms	14556 KB	Output is correct
22	Correct	13 ms	15588 KB	Output is correct
23	Correct	11 ms	15592 KB	Output is correct
24	Correct	12 ms	15576 KB	Output is correct
25	Correct	11 ms	15604 KB	Output is correct
26	Correct	13 ms	15572 KB	Output is correct
27	Correct	11 ms	15552 KB	Output is correct
28	Correct	12 ms	15572 KB	Output is correct
29	Correct	14 ms	15604 KB	Output is correct
30	Correct	11 ms	15572 KB	Output is correct
31	Correct	11 ms	15588 KB	Output is correct
32	Correct	11 ms	15596 KB	Output is correct
33	Correct	11 ms	15720 KB	Output is correct
34	Correct	11 ms	15520 KB	Output is correct
35	Correct	12 ms	15588 KB	Output is correct
36	Correct	11 ms	15572 KB	Output is correct
37	Correct	12 ms	15572 KB	Output is correct
38	Correct	11 ms	15600 KB	Output is correct

Subtask #3
80.0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	14548 KB	Output is correct
2	Correct	7 ms	14548 KB	Output is correct
3	Correct	7 ms	14548 KB	Output is correct
4	Correct	9 ms	14548 KB	Output is correct
5	Correct	8 ms	14548 KB	Output is correct
6	Correct	8 ms	14548 KB	Output is correct
7	Correct	9 ms	14544 KB	Output is correct
8	Correct	8 ms	14548 KB	Output is correct
9	Correct	7 ms	14548 KB	Output is correct
10	Correct	8 ms	14548 KB	Output is correct
11	Correct	7 ms	14556 KB	Output is correct
12	Correct	7 ms	14552 KB	Output is correct
13	Correct	7 ms	14548 KB	Output is correct
14	Correct	7 ms	14548 KB	Output is correct
15	Correct	7 ms	14508 KB	Output is correct
16	Correct	7 ms	14536 KB	Output is correct
17	Correct	7 ms	14552 KB	Output is correct
18	Correct	7 ms	14548 KB	Output is correct
19	Correct	7 ms	14552 KB	Output is correct
20	Correct	7 ms	14556 KB	Output is correct
21	Correct	8 ms	14556 KB	Output is correct
22	Correct	13 ms	15588 KB	Output is correct
23	Correct	11 ms	15592 KB	Output is correct
24	Correct	12 ms	15576 KB	Output is correct
25	Correct	11 ms	15604 KB	Output is correct
26	Correct	13 ms	15572 KB	Output is correct
27	Correct	11 ms	15552 KB	Output is correct
28	Correct	12 ms	15572 KB	Output is correct
29	Correct	14 ms	15604 KB	Output is correct
30	Correct	11 ms	15572 KB	Output is correct
31	Correct	11 ms	15588 KB	Output is correct
32	Correct	11 ms	15596 KB	Output is correct
33	Correct	11 ms	15720 KB	Output is correct
34	Correct	11 ms	15520 KB	Output is correct
35	Correct	12 ms	15588 KB	Output is correct
36	Correct	11 ms	15572 KB	Output is correct
37	Correct	12 ms	15572 KB	Output is correct
38	Correct	11 ms	15600 KB	Output is correct
39	Correct	465 ms	65136 KB	Output is correct
40	Correct	447 ms	64296 KB	Output is correct
41	Correct	450 ms	65300 KB	Output is correct
42	Correct	504 ms	65980 KB	Output is correct
43	Correct	474 ms	66084 KB	Output is correct
44	Correct	469 ms	66064 KB	Output is correct
45	Correct	532 ms	69816 KB	Output is correct
46	Correct	340 ms	71924 KB	Output is correct
47	Correct	437 ms	67584 KB	Output is correct
48	Correct	406 ms	68100 KB	Output is correct
49	Correct	450 ms	66784 KB	Output is correct
50	Correct	390 ms	68168 KB	Output is correct
51	Correct	358 ms	72404 KB	Output is correct

Submission #544618

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 16.0 / 16.0

Subtask #3 80.0 / 80.0

Subtask #1
4.0 / 4.0

Subtask #2
16.0 / 16.0

Subtask #3
80.0 / 80.0