제출 #398190

#제출 시각아이디문제언어결과실행 시간메모리
398190ChrisTMeetings 2 (JOI21_meetings2)C++17
100 / 100
1079 ms24324 KiB
#include <bits/stdc++.h> using namespace std; const int MN = 2e5 + 5; vector<int> adj[MN]; bool vis[MN]; int sz[MN], ans[MN], bit[MN], cent; vector<array<int,2>> toadd; void update (int i, int v) { for (i=MN-i;i<MN;i+=i&-i) bit[i] = max(bit[i],v); } int query (int i) { int ret = -1e9; for (i=MN-i;i;i^=i&-i) ret = max(ret,bit[i]); return ret; } void clear (int i) { for (i=MN-i;i;i^=i&-i) bit[i] = 0; } void getsz (int cur, int p = -1) { sz[cur] = 1; for (int i : adj[cur]) if (!vis[i] && i != p) { getsz(i,cur); sz[cur] += sz[i]; } } int getcent (int cur, int tot, int p = -1) { for (int i : adj[cur]) if (!vis[i] && i != p && sz[i] > tot/2) return getcent(i,tot,cur); return cur; } void dfs (int cur, int ch, int depth = 1, int p = -1) { toadd.push_back({sz[cur],depth}); ans[sz[cur]*2] = max(ans[sz[cur]*2],depth + query(sz[cur]) + 1); if (sz[cent] - sz[ch] >= sz[cur]) ans[sz[cur]*2] = max(ans[sz[cur]*2],depth + 1); for (int i : adj[cur]) if (i != p && !vis[i]) { dfs(i,ch,depth+1,cur); } } void decomp (int cur) { getsz(cur); cent = getcent(cur,sz[cur]); vis[cent] = 1; getsz(cent); for (int i : adj[cent]) if (!vis[i]) { dfs(i,i); for (auto &[s,d] : toadd) update(s,d); toadd.clear(); } for (int i = 1; i <= sz[cent]; i++) clear(i); reverse(adj[cent].begin(),adj[cent].end()); for (int i : adj[cent]) if (!vis[i]) { dfs(i,i); for (auto &[s,d] : toadd) update(s,d); toadd.clear(); } for (int i = 1; i <= sz[cent]; i++) clear(i); for (int i : adj[cent]) if (!vis[i]) decomp(i); } int main () { int n; scanf ("%d",&n); for (int i = 1; i < n; i++) { int a,b; scanf ("%d %d",&a,&b); adj[a].push_back(b); adj[b].push_back(a); } decomp(1); for (int i = n - (n%2); i > 2; i -= 2) ans[i-2] = max(ans[i-2],ans[i]); for (int i = 1; i <= n; i++) printf ("%d\n",i&1?1:max(1,ans[i])); return 0; }

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

meetings2.cpp: In function 'int main()':
meetings2.cpp:61:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |  int n; scanf ("%d",&n);
      |         ~~~~~~^~~~~~~~~
meetings2.cpp:63:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |   int a,b; scanf ("%d %d",&a,&b);
      |            ~~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...