oj.uz

답안 #1100915

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1100915 2024-10-15T03:14:22 Z BuiDucManh123 Meetings 2 (JOI21_meetings2) C++14
0 / 100
 2 ms 10832 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define taskname ""
#define int ll
using namespace std;
ll sz[200009],ma[200009],pre[200009],i,m,n,u,v,ans[200009],check[200009],maxdepth;
vector<int>g[200009];
void dfs(int id,int par){
    sz[id]=1;
    for(int x:g[id]){
        if(x==par||check[x]) continue;
        dfs(x,id);
        sz[id]+=sz[x];
    }
}
int centroid(int id,int par,int siz){
    for(int u:g[id]){
        if(u==par||check[u]) continue;
        if(sz[u]*2>=siz) return centroid(u,id,siz);
    }return id;
}
void dfs2(int id,int par,int h,int siz){
    //maxdepth=max(maxdepth,sz[id]);
    ans[min(siz,sz[id])*2]=max(ans[min(siz,sz[id])*2],h);
    ma[sz[id]]=max(ma[sz[id]],h);
    for(int u:g[id]){
        if(u==par||check[u]) continue;
        dfs2(u,id,h+1,siz);
    }
}
void solve(int id){
    dfs(id,0);
    int c=centroid(id,0,sz[id]);
    //cout<<c<<" ";
    check[c]=1;
    dfs(c,0);
    //check[c]=1;
    maxdepth=0;
    for(int u:g[c]){
        if(check[u]) continue;
        dfs2(u,c,2,sz[c]-sz[u]);
        maxdepth=max(maxdepth,sz[u]);
        for(int i=sz[u]-1;i>=1;i--) ma[i]=max(ma[i],ma[i+1]);
        //ans[]
        for(int i=sz[u];i>=1;i--){
            ans[i*2]=max(ans[i*2],ma[i]+pre[i]-1);
            pre[i]=max(pre[i],ma[i]);
        }
        for(int i=1;i<=sz[u];i++) ma[i]=0;
    }
    for(int i=1;i<=maxdepth;i++) pre[i]=0,ma[i]=0;
    for(int u:g[c]){
        if(check[u]) continue;
        solve(u);
    }
}
signed main() {
	if (fopen(taskname".inp","r")) {
		freopen(taskname".inp","r",stdin);
		freopen(taskname".out","w",stdout);
	}
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    cin>>n;
    for(i=1;i<n;i++){
        cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
    }
    solve(1);
    for(i=1;i<=n;i++){
        if(i&1) cout<<1<<"\n";
        else cout<<ans[i]<<"\n";
    }
	return 0;
}

Compilation message

meetings2.cpp: In function 'int main()':
meetings2.cpp:65:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |   freopen(taskname".inp","r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
meetings2.cpp:66:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |   freopen(taskname".out","w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10832 KB Output is correct
2 Correct 2 ms 10832 KB Output is correct
3 Correct 2 ms 10832 KB Output is correct
4 Incorrect 2 ms 10832 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10832 KB Output is correct
2 Correct 2 ms 10832 KB Output is correct
3 Correct 2 ms 10832 KB Output is correct
4 Incorrect 2 ms 10832 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10832 KB Output is correct
2 Correct 2 ms 10832 KB Output is correct
3 Correct 2 ms 10832 KB Output is correct
4 Incorrect 2 ms 10832 KB Output isn't correct
5 Halted 0 ms 0 KB -