제출 #596484

#제출 시각아이디문제언어결과실행 시간메모리
596484keta_tsimakuridzeMeetings 2 (JOI21_meetings2)C++14
100 / 100
1072 ms59800 KiB
#include<bits/stdc++.h> #define f first #define s second #define pii pair<int,int> #define Pii pair<pair<int,int> , pair<int,int> > using namespace std; const int N = 2e5 + 5, mod = 1e9 + 7; // ! int t, sz[N], f[N], h; int n, c; int ans[N]; map<int,int> SZ[N]; vector<pair<int, pair<int,int> > > x; vector<int> V[N]; int find(int u,int p, int Sz) { for(int i = 0; i< V[u].size(); i++) { if(V[u][i] == p|| f[V[u][i]]) continue; if(sz[V[u][i]] > Sz / 2) return find(V[u][i], u, Sz); } return u; } void dfs(int u, int p) { sz[u] = 1; for(int i = 0; i < V[u].size(); i++) { if(V[u][i] == p || f[V[u][i]]) continue; dfs(V[u][i], u); sz[u] += sz[V[u][i]]; } } void dfs(int u,int p,int P) { ++h; x.push_back({SZ[p][u], {h, P}}); ans[min(SZ[p][u], n - SZ[c][P]) * 2] = max(ans[min(SZ[p][u], n - SZ[c][P]) * 2], h + 1); for(int i = 0; i < V[u].size(); i++) { if(V[u][i] == p || f[V[u][i]]) continue; dfs(V[u][i], u, P); } --h; } void upd(Pii &mx, pii x) { if(x.s == mx.f.s) mx.f = max(mx.f, x); else mx.s = max(mx.s, x); if(mx.f.f < mx.s.f) swap(mx.s, mx.f); } void decomp(int U) { dfs(U, 0); c = find(U, 0, sz[U]); for(int i = 0; i < V[c].size(); i++) { if(f[V[c][i]] == 0) dfs(V[c][i], c, V[c][i]); } pair<pii, pii> mx; mx = {{-n, 0}, {-n, 0}}; sort(x.begin(), x.end()); while(x.size()) { int i = x.back().f; pii y = x.back().s; ans[i * 2] = max(ans[i * 2], y.f + (mx.f.s != y.s ? mx.f.f : mx.s.f ) + 1); upd(mx, y); x.pop_back(); } f[c] = 1; int C = c; for(int i = 0; i < V[C].size(); i++) { if(!f[V[C][i]]) decomp(V[C][i]); } } void dfss(int u,int p) { sz[u] = 1; for(int i = 0; i < V[u].size(); i++) { if(V[u][i] == p) continue; dfss(V[u][i], u); SZ[u][V[u][i]] = sz[V[u][i]]; sz[u] += sz[V[u][i]]; } SZ[u][p] = n - sz[u]; } main(){ cin >> n; for(int i = 1; i < n; i++) { int u, v; cin >> u >> v; V[u].push_back(v); V[v].push_back(u); } dfss(1, 0); decomp(1); for(int i = n; i >= 1; i--) { ans[i] = (i % 2 == 0 ? max(ans[i], ans[i + 2]) : 1); } for(int i = 1; i <= n; i++) { ans[i] = max(ans[i], 1); cout << ans[i] << "\n"; } }

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

meetings2.cpp: In function 'int find(int, int, int)':
meetings2.cpp:15:21: 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< V[u].size(); i++) {
      |                    ~^~~~~~~~~~~~~
meetings2.cpp: In function 'void dfs(int, int)':
meetings2.cpp:23:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(int i = 0; i < V[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
meetings2.cpp: In function 'void dfs(int, int, int)':
meetings2.cpp:33:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for(int i = 0; i < V[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
meetings2.cpp: In function 'void decomp(int)':
meetings2.cpp:47:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i = 0; i < V[c].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
meetings2.cpp:63:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(int i = 0; i < V[C].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
meetings2.cpp: In function 'void dfss(int, int)':
meetings2.cpp:69:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for(int i = 0; i < V[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
meetings2.cpp: At global scope:
meetings2.cpp:77:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   77 | main(){
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...