| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 584248 |
2022-06-27T05:31:13 Z |
반딧불(#8375) |
Meetings 2 (JOI21_meetings2) |
C++17 |
|
4000 ms |
33032 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
vector<int> link[200002];
int in[200002], out[200002], inCnt, sz[200002], depth[200002], par[200002];
int LCADB[200002][20];
int ans[200002];
void dfs(int x, int p=-1){
in[x] = ++inCnt;
sz[x] = 1;
for(auto y: link[x]){
if(y==p) continue;
depth[y] = depth[x]+1;
dfs(y, x);
par[y] = x;
sz[x] += sz[y];
}
out[x] = inCnt;
}
void constructLCA(){
for(int i=1; i<=n; i++) LCADB[i][0] = par[i];
for(int d=1; d<20; d++) for(int i=1; i<=n; i++) LCADB[i][d] = LCADB[LCADB[i][d-1]][d-1];
}
int getLCA(int x, int y){
if(depth[x] > depth[y]) swap(x, y);
for(int d=0; d<20; d++) if((depth[y]-depth[x])&(1<<d)) y = LCADB[y][d];
if(x==y) return x;
for(int d=19; d>=0; d--) if(LCADB[x][d] != LCADB[y][d]) x = LCADB[x][d], y = LCADB[y][d];
return par[x];
}
int kthParent(int x, int d){
for(int i=0; i<20; i++) if((d>>i)&1) x = LCADB[x][i];
return x;
}
void calc(int x, int y){
if(in[x] > in[y]) swap(x, y);
if(out[x] < in[y]){ /// �θ� �ڽ� ���谡 �ƴ�
int val = min(sz[x], sz[y]);
int d = depth[x] + depth[y] - 2 * depth[getLCA(x, y)];
ans[val] = max(ans[val], d);
}
else{ /// x�� y�� ����
int val = min(n-sz[kthParent(y, depth[y]-depth[x]-1)], sz[y]);
int d = depth[y] - depth[x];
ans[val] = max(ans[val], d);
}
}
int main(){
scanf("%d", &n);
for(int i=1; i<n; i++){
int x, y;
scanf("%d %d", &x, &y);
link[x].push_back(y);
link[y].push_back(x);
}
dfs(1);
constructLCA();
for(int i=1; i<=n; i++){
for(int j=i+1; j<=n; j++){
calc(i, j);
}
}
for(int i=n; i>=1; i--) ans[i] = max(ans[i+1], ans[i]);
for(int i=1; i<=n; i++){
if(i&1) printf("1\n");
else printf("%d\n", ans[i/2]+1);
}
}
Compilation message
meetings2.cpp: In function 'int main()':
meetings2.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
59 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
meetings2.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
62 | scanf("%d %d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5020 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5008 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 7 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 8 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 9 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 10 |
Correct |
4 ms |
4948 KB |
Output is correct |
| 11 |
Correct |
3 ms |
5012 KB |
Output is correct |
| 12 |
Correct |
3 ms |
5008 KB |
Output is correct |
| 13 |
Correct |
3 ms |
5004 KB |
Output is correct |
| 14 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 15 |
Correct |
4 ms |
4948 KB |
Output is correct |
| 16 |
Correct |
3 ms |
5004 KB |
Output is correct |
| 17 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 18 |
Correct |
3 ms |
5008 KB |
Output is correct |
| 19 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 20 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 21 |
Correct |
3 ms |
4948 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5020 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5008 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 7 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 8 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 9 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 10 |
Correct |
4 ms |
4948 KB |
Output is correct |
| 11 |
Correct |
3 ms |
5012 KB |
Output is correct |
| 12 |
Correct |
3 ms |
5008 KB |
Output is correct |
| 13 |
Correct |
3 ms |
5004 KB |
Output is correct |
| 14 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 15 |
Correct |
4 ms |
4948 KB |
Output is correct |
| 16 |
Correct |
3 ms |
5004 KB |
Output is correct |
| 17 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 18 |
Correct |
3 ms |
5008 KB |
Output is correct |
| 19 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 20 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 21 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 22 |
Correct |
700 ms |
5588 KB |
Output is correct |
| 23 |
Correct |
687 ms |
5588 KB |
Output is correct |
| 24 |
Correct |
729 ms |
5604 KB |
Output is correct |
| 25 |
Correct |
709 ms |
5588 KB |
Output is correct |
| 26 |
Correct |
668 ms |
5588 KB |
Output is correct |
| 27 |
Correct |
688 ms |
5584 KB |
Output is correct |
| 28 |
Correct |
738 ms |
5588 KB |
Output is correct |
| 29 |
Correct |
671 ms |
5588 KB |
Output is correct |
| 30 |
Correct |
692 ms |
5588 KB |
Output is correct |
| 31 |
Correct |
674 ms |
5588 KB |
Output is correct |
| 32 |
Correct |
1016 ms |
5688 KB |
Output is correct |
| 33 |
Correct |
959 ms |
5784 KB |
Output is correct |
| 34 |
Correct |
595 ms |
5588 KB |
Output is correct |
| 35 |
Correct |
526 ms |
5596 KB |
Output is correct |
| 36 |
Correct |
907 ms |
5612 KB |
Output is correct |
| 37 |
Correct |
585 ms |
5596 KB |
Output is correct |
| 38 |
Correct |
762 ms |
5676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5020 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5008 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 7 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 8 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 9 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 10 |
Correct |
4 ms |
4948 KB |
Output is correct |
| 11 |
Correct |
3 ms |
5012 KB |
Output is correct |
| 12 |
Correct |
3 ms |
5008 KB |
Output is correct |
| 13 |
Correct |
3 ms |
5004 KB |
Output is correct |
| 14 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 15 |
Correct |
4 ms |
4948 KB |
Output is correct |
| 16 |
Correct |
3 ms |
5004 KB |
Output is correct |
| 17 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 18 |
Correct |
3 ms |
5008 KB |
Output is correct |
| 19 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 20 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 21 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 22 |
Correct |
700 ms |
5588 KB |
Output is correct |
| 23 |
Correct |
687 ms |
5588 KB |
Output is correct |
| 24 |
Correct |
729 ms |
5604 KB |
Output is correct |
| 25 |
Correct |
709 ms |
5588 KB |
Output is correct |
| 26 |
Correct |
668 ms |
5588 KB |
Output is correct |
| 27 |
Correct |
688 ms |
5584 KB |
Output is correct |
| 28 |
Correct |
738 ms |
5588 KB |
Output is correct |
| 29 |
Correct |
671 ms |
5588 KB |
Output is correct |
| 30 |
Correct |
692 ms |
5588 KB |
Output is correct |
| 31 |
Correct |
674 ms |
5588 KB |
Output is correct |
| 32 |
Correct |
1016 ms |
5688 KB |
Output is correct |
| 33 |
Correct |
959 ms |
5784 KB |
Output is correct |
| 34 |
Correct |
595 ms |
5588 KB |
Output is correct |
| 35 |
Correct |
526 ms |
5596 KB |
Output is correct |
| 36 |
Correct |
907 ms |
5612 KB |
Output is correct |
| 37 |
Correct |
585 ms |
5596 KB |
Output is correct |
| 38 |
Correct |
762 ms |
5676 KB |
Output is correct |
| 39 |
Execution timed out |
4067 ms |
33032 KB |
Time limit exceeded |
| 40 |
Halted |
0 ms |
0 KB |
- |
