제출 #1033962

#제출 시각아이디문제언어결과실행 시간메모리
1033962vjudge1Meetings 2 (JOI21_meetings2)C++17
0 / 100
1 ms10588 KiB
#include<bits/stdc++.h> #define int long long #define ll pair<int,int> using namespace std; const int N=200022; vector<int> ke[N]; int maxx[N]; int h[N]; int kq[N]; int oo=1e9; int kq2[N]; int sz[N]; void dfs(int u,int pa) { sz[u]=1; for (int i=0;i<ke[u].size();i++) { int v=ke[u][i]; if (v==pa) continue; dfs(v,u); sz[u]+=sz[v]; } } int dfs2(int u,int pa,int kk) { for (int i=0;i<ke[u].size();i++) { int v=ke[u][i]; if (v==pa) continue; if (sz[v]>kk/2) return dfs2(v,u,kk); } return u; } void dfs3(int u,int pa,int kk) { sz[u]=1; h[u]=kk; for (int i=0;i<ke[u].size();i++) { int v=ke[u][i]; if (v==pa) continue; dfs3(v,u,kk+1); sz[u]+=sz[v]; } kq[sz[u]]=max(kq[sz[u]],h[u]); } signed main() { // freopen("kk.inp","r",stdin); // freopen("kk.out","w",stdout); // freopen("City.inp","r",stdin); // freopen("City.out","w",stdout); ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); int n; cin >> n; for (int i=1;i<n;i++) { int u,v; cin >> u >> v; ke[u].push_back(v); ke[v].push_back(u); } dfs(1,0); int dinh=dfs2(1,0,sz[1]); h[dinh]=0; for (int i=1;i<=n;i++) kq[i]=maxx[i]=-oo; for (int i=0;i<ke[dinh].size();i++) { int v=ke[dinh][i]; dfs3(v,dinh,1); kq[sz[v]+1]=0; for (int i2=sz[v]+1;i2>=2;i2--) kq[i2-1]=max(kq[i2-1],kq[i2]); for (int i2=1;i2<=sz[v]+1;i2++) { kq2[i2*2]=max(kq2[i2*2],kq[i2]+maxx[i2]); } for (int i2=1;i2<=sz[v]+1;i2++) { maxx[i2]=max(maxx[i2],kq[i2]); kq[i2]=-oo; } } for (int i=1;i<=n;i++) { cout << kq2[i]+1 << '\n'; } }

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

meetings2.cpp: In function 'void dfs(long long int, long long int)':
meetings2.cpp:18:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for (int i=0;i<ke[u].size();i++)
      |                  ~^~~~~~~~~~~~~
meetings2.cpp: In function 'long long int dfs2(long long int, long long int, long long int)':
meetings2.cpp:29:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i=0;i<ke[u].size();i++)
      |                  ~^~~~~~~~~~~~~
meetings2.cpp: In function 'void dfs3(long long int, long long int, long long int)':
meetings2.cpp:42:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (int i=0;i<ke[u].size();i++)
      |                  ~^~~~~~~~~~~~~
meetings2.cpp: In function 'int main()':
meetings2.cpp:74:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for (int i=0;i<ke[dinh].size();i++)
      |                  ~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...