Submission #914871

#TimeUsernameProblemLanguageResultExecution timeMemory
914871alexander707070Meetings 2 (JOI21_meetings2)C++14
20 / 100
4037 ms22052 KiB
#include<bits/stdc++.h> #define MAXN 300007 using namespace std; struct dude{ int h,l; }; int n,a,b,sz[MAXN],root,parent[MAXN],pt[MAXN],ans[MAXN]; int dist[MAXN],maxs; vector<int> v[MAXN]; bool used[MAXN]; void dfs(int x,int p){ sz[x]=1; parent[x]=p; for(int i=0;i<v[x].size();i++){ if(v[x][i]==p)continue; dfs(v[x][i],x); sz[x]+=sz[v[x][i]]; } } int centroid(int x,int p){ for(int i=0;i<v[x].size();i++){ if(v[x][i]==p)continue; if(sz[v[x][i]]>n/2){ return centroid(v[x][i],x); } } return x; } void dfs1(int x,int p,int d){ dist[x]=d; for(int i=0;i<v[x].size();i++){ if(v[x][i]==p or used[v[x][i]])continue; dfs1(v[x][i],x,d+1); } } int diameter(){ for(int i=1;i<=n;i++){ if(used[i])continue; dfs1(i,0,0); break; } maxs=0; for(int i=1;i<=n;i++){ if(used[i])continue; if(dist[i]>dist[maxs])maxs=i; } dfs1(maxs,0,0); maxs=0; for(int i=1;i<=n;i++){ if(used[i])continue; maxs=max(maxs,dist[i]); } return maxs+1; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n; for(int i=1;i<=n-1;i++){ cin>>a>>b; v[a].push_back(b); v[b].push_back(a); } dfs(1,0); root=centroid(1,0); dfs(root,0); for(int i=1;i<=n;i++)pt[i]=i; for(int k=1;k<=n/2;k++){ for(int i=1;i<=n;i++){ while(sz[pt[i]]<k){ used[pt[i]]=true; pt[i]=parent[pt[i]]; } } ans[2*k]=diameter(); } for(int i=1;i<=n;i++){ if(i%2==1)cout<<"1\n"; else cout<<ans[i]<<"\n"; } return 0; }

Compilation message (stderr)

meetings2.cpp: In function 'void dfs(int, int)':
meetings2.cpp:17:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
meetings2.cpp: In function 'int centroid(int, int)':
meetings2.cpp:25:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
meetings2.cpp: In function 'void dfs1(int, int, int)':
meetings2.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...