| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 584252 |
2022-06-27T05:50:12 Z |
조영욱(#8377) |
Meetings 2 (JOI21_meetings2) |
C++17 |
|
3 ms |
4948 KB |
#include <bits/stdc++.h>
using namespace std;
int sz[200001];
vector<int> adj[200001];
typedef pair<int,int> P;
P val[200001];
int ret[100001];
int table[100001][17];
int dep[100001];
void dfs(int v,int prev) {
sz[v]=1;
table[v][0]=prev;
for(int i=0;i<adj[v].size();i++) {
int nt=adj[v][i];
if (nt==prev) {
continue;
}
dep[nt]=dep[v]+1;
dfs(nt,v);
sz[v]+=sz[nt];
}
}
int getcent(int v,int prev,int half) {
for(int i=0;i<adj[v].size();i++) {
int nt=adj[v][i];
if (nt==prev) {
continue;
}
if (sz[nt]>half) {
return getcent(nt,v,half);
}
}
return v;
}
int lca(int a,int b) {
if (dep[a]<dep[b]) {
swap(a,b);
}
int diff=dep[a]-dep[b];
for(int i=0;diff;i++) {
if (diff&1) {
a=table[a][i];
}
diff/=2;
}
for(int i=16;i>=0;i--) {
if (table[a][i]!=0&&table[a][i]!=table[b][i]) {
a=table[a][i];
b=table[b][i];
}
}
return table[a][0];
}
int dist(int a,int b) {
return dep[a]+dep[b]-2*dep[lca(a,b)];
}
int main() {
int n;
scanf("%d",&n);
for(int i=1;i<n;i++) {
int u,v;
scanf("%d %d",&u,&v);
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1,0);
int c=getcent(1,0,n/2);
dep[c]=0;
dfs(c,0);
for(int j=1;j<17;j++) {
for(int i=1;i<=n;i++) {
if (table[i][j-1]!=0) {
table[i][j]=table[table[i][j-1]][j-1];
}
}
}
for(int i=1;i<=n;i++) {
val[i].first=n;
if (i==c) {
int mx=0;
for(int j=0;j<adj[i].size();j++) {
mx=max(mx,sz[adj[i][j]]);
}
val[i].first=n-mx;
}
else {
val[i].first=sz[i];
}
//printf("%d\n",val[i].first);
val[i].second=i;
}
sort(val+1,val+n+1);
reverse(val+1,val+n+1);
int ind=1;
int one=0;
int two=0;
int mx=-1;
for(int i=n;i>0;i--) {
while (ind<=n&&val[ind].first==i) {
int now=val[ind].second;
if (one==0) {
one=now;
two=now;
mx=0;
continue;
}
if (dist(one,now)>mx) {
mx=dist(one,now);
two=now;
}
else if (dist(now,two)>mx) {
mx=dist(now,two);
one=now;
}
ind++;
}
if (i<=n/2)
ret[i]=mx+1;
}
for(int i=1;i<=n;i++) {
printf("%d\n",i%2==0?ret[i/2]:1);
}
return 0;
}
Compilation message
meetings2.cpp: In function 'void dfs(int, int)':
meetings2.cpp:15:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | for(int i=0;i<adj[v].size();i++) {
| ~^~~~~~~~~~~~~~
meetings2.cpp: In function 'int getcent(int, int, int)':
meetings2.cpp:27:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | for(int i=0;i<adj[v].size();i++) {
| ~^~~~~~~~~~~~~~
meetings2.cpp: In function 'int main()':
meetings2.cpp:87:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for(int j=0;j<adj[i].size();j++) {
| ~^~~~~~~~~~~~~~
meetings2.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
65 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
meetings2.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
68 | scanf("%d %d",&u,&v);
| ~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
