제출 #976503

#제출 시각아이디문제언어결과실행 시간메모리
976503happy_nodeMeetings 2 (JOI21_meetings2)C++17
0 / 100
2 ms10072 KiB
#include <bits/stdc++.h> using namespace std; const int MX=2e5+5; int N; vector<int> adj[MX]; bool used[MX]; int sz[MX]; pair<int,int> f[MX], ff[MX]; // max_1, max_2 int getSize(int v, int p) { sz[v]=1; for(auto u:adj[v]) { if(u==p || used[u]) continue; sz[v]+=getSize(u,v); } return sz[v]; } int getCen(int v, int p, int s) { for(auto u:adj[v]) { if(u==p || used[u]) continue; if(2*sz[u]>s) return getCen(u,v,s); } return v; } int head=0; int ans[MX]; void dfs(int v, int p, int dep) { if(make_pair(dep,head)>f[sz[v]]) { ff[sz[v]]=f[sz[v]]; f[sz[v]]=make_pair(dep,head); } else if(make_pair(dep,head)>ff[sz[v]]) { ff[sz[v]]=make_pair(dep,head); } for(auto u:adj[v]) { if(u==p || used[u]) continue; dfs(u,v,dep+1); } } void cdc(int v) { int s=getSize(v,v); int cen=getCen(v,v,s); used[cen]=true; getSize(cen,cen); for(auto u:adj[cen]) { if(!used[u]) { head=u; dfs(u,cen,1); } } vector<pair<int,int>> vv; for(int i=s;i>=1;i--) { vv.push_back(f[i]); vv.push_back(ff[i]); sort(vv.rbegin(),vv.rend()); while(vv.size()>3) vv.pop_back(); for(int j=0;j<vv.size();j++) { for(int k=j+1;k<vv.size();k++) { if(vv[j].second!=vv[k].second) ans[2*i]=max(ans[2*i],vv[j].first+vv[k].first+1); } } } for(int i=1;i<=s;i++) { f[i]={0,0}; ff[i]={0,0}; } for(auto u:adj[cen]) { if(!used[u]) { cdc(u); } } } int main() { cin.tie(0); ios_base::sync_with_stdio(0); cin>>N; for(int i=1;i<N;i++) { int u,v; cin>>u>>v; adj[u].push_back(v); adj[v].push_back(u); } cdc(1); for(int i=1;i<=N;i++) { if(i&1) { cout<<1<<'\n'; } else { cout<<ans[i]<<'\n'; } } }

컴파일 시 표준 에러 (stderr) 메시지

meetings2.cpp: In function 'void cdc(int)':
meetings2.cpp:67:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   for(int j=0;j<vv.size();j++) {
      |               ~^~~~~~~~~~
meetings2.cpp:68:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |    for(int k=j+1;k<vv.size();k++) {
      |                  ~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...