oj.uz

Submission #893663

# Submission time Handle Problem Language Result Execution time Memory
893663 2023-12-27T08:51:14 Z 8pete8 Meetings 2 (JOI21_meetings2) C++17
100 / 100
 393 ms 32520 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<float.h>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<pii,int>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
#define int long long
using namespace std;
const int mod=998244353,mxn=2e5+5,lg=30,inf=1e9,minf=-1e9,Mxn=100000;
int n,sz[mxn+10],h[mxn+10],mx[mxn+10],ans[mxn+10];
pair<pii,pii> v[mxn+10];
vector<int>adj[mxn+10];
bitset<mxn+10>del;
void getsz(int cur,int p){
    sz[cur]=1;
    for(auto i:adj[cur]){
        if(i==p||del[i])continue;
        getsz(i,cur);
        sz[cur]+=sz[i];
    }
}
int getcen(int cur,int p,int need){
    for(auto i:adj[cur])if(!del[i]&&i!=p&&sz[i]*2>need)return getcen(i,cur,need);
    return cur;
}
int cnt=0;
void dfs(int cur,int p){
    sz[cur]=1;
    for(auto i:adj[cur]){
        if(i==p||del[i])continue;
        h[i]=h[cur]+1;
        dfs(i,cur);
        sz[cur]+=sz[i];
    }
    mx[sz[cur]]=max(mx[sz[cur]],h[cur]);
}
void solve(int root){
    if(del[root])assert(0);
    getsz(root,-1);
    int node=getcen(root,-1,sz[root]);
    h[node]=0;
    int sum=sz[root];
    cnt=0;
    for(auto i:adj[node]){
        if(del[i]){
            cnt++;
            continue;
        }
        h[i]=1;
        dfs(i,node);
        mx[sz[i]+1]=minf;
        for(int j=sz[i];j>=0;j--){
            mx[j]=max(mx[j],mx[j+1]);
            if(mx[j]==minf)continue;
            if(v[j].f.f==-1||v[j].f.f<mx[j]){
                swap(v[j].f,v[j].s);
                v[j].f={mx[j],cnt};
            }
            else if(v[j].s.f==-1||v[j].s.f<mx[j])v[j].s={mx[j],cnt};
        }
        for(int j=0;j<=sz[i];j++)mx[j]=minf;
        cnt++;
    }
    int cmx=minf;
    for(int i=sum;i>=0;i--){
        if(v[i].f.f==-1)continue;
        if(v[i].f.s<0)assert(0);
        if(v[i].s.f==-1&&sum-sz[adj[node][v[i].f.s]]>=i)cmx=max(cmx,v[i].f.f);
        else if(v[i].s.f!=-1) cmx=max(cmx,v[i].f.f+v[i].s.f);
        ans[i]=max(ans[i],cmx);
        v[i]={{-1,-1},{-1,-1}};
    }
    del[node]=true;
    for(auto i:adj[node])if(!del[i])solve(i);
}
int32_t main(){
    cin>>n;
    for(int i=0;i<n-1;i++){
        int u,v;cin>>u>>v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    for(int i=0;i<=n;i++)v[i]={{-1,-1},{-1,-1}};
    fill(mx,mx+mxn+5,minf);
    solve(1);
    for(int i=1;i<=n;i++){
        if(i&1)cout<<1<<'\n';
        else cout<<ans[i/2]+1<<'\n';
    }
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10852 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 3 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10832 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 2 ms 10840 KB Output is correct
10 Correct 2 ms 10844 KB Output is correct
11 Correct 2 ms 10840 KB Output is correct
12 Correct 2 ms 10844 KB Output is correct
13 Correct 2 ms 10844 KB Output is correct
14 Correct 2 ms 10844 KB Output is correct
15 Correct 2 ms 10844 KB Output is correct
16 Correct 2 ms 10844 KB Output is correct
17 Correct 2 ms 10844 KB Output is correct
18 Correct 2 ms 10832 KB Output is correct
19 Correct 2 ms 10844 KB Output is correct
20 Correct 2 ms 10844 KB Output is correct
21 Correct 2 ms 10840 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10852 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 3 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10832 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 2 ms 10840 KB Output is correct
10 Correct 2 ms 10844 KB Output is correct
11 Correct 2 ms 10840 KB Output is correct
12 Correct 2 ms 10844 KB Output is correct
13 Correct 2 ms 10844 KB Output is correct
14 Correct 2 ms 10844 KB Output is correct
15 Correct 2 ms 10844 KB Output is correct
16 Correct 2 ms 10844 KB Output is correct
17 Correct 2 ms 10844 KB Output is correct
18 Correct 2 ms 10832 KB Output is correct
19 Correct 2 ms 10844 KB Output is correct
20 Correct 2 ms 10844 KB Output is correct
21 Correct 2 ms 10840 KB Output is correct
22 Correct 5 ms 10844 KB Output is correct
23 Correct 6 ms 10844 KB Output is correct
24 Correct 4 ms 10888 KB Output is correct
25 Correct 6 ms 11096 KB Output is correct
26 Correct 5 ms 10840 KB Output is correct
27 Correct 5 ms 10844 KB Output is correct
28 Correct 5 ms 10844 KB Output is correct
29 Correct 5 ms 10844 KB Output is correct
30 Correct 5 ms 11188 KB Output is correct
31 Correct 6 ms 10844 KB Output is correct
32 Correct 5 ms 11100 KB Output is correct
33 Correct 5 ms 11100 KB Output is correct
34 Correct 4 ms 10844 KB Output is correct
35 Correct 4 ms 10844 KB Output is correct
36 Correct 4 ms 11032 KB Output is correct
37 Correct 5 ms 10844 KB Output is correct
38 Correct 4 ms 11100 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10852 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 3 ms 10844 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10832 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 2 ms 10840 KB Output is correct
10 Correct 2 ms 10844 KB Output is correct
11 Correct 2 ms 10840 KB Output is correct
12 Correct 2 ms 10844 KB Output is correct
13 Correct 2 ms 10844 KB Output is correct
14 Correct 2 ms 10844 KB Output is correct
15 Correct 2 ms 10844 KB Output is correct
16 Correct 2 ms 10844 KB Output is correct
17 Correct 2 ms 10844 KB Output is correct
18 Correct 2 ms 10832 KB Output is correct
19 Correct 2 ms 10844 KB Output is correct
20 Correct 2 ms 10844 KB Output is correct
21 Correct 2 ms 10840 KB Output is correct
22 Correct 5 ms 10844 KB Output is correct
23 Correct 6 ms 10844 KB Output is correct
24 Correct 4 ms 10888 KB Output is correct
25 Correct 6 ms 11096 KB Output is correct
26 Correct 5 ms 10840 KB Output is correct
27 Correct 5 ms 10844 KB Output is correct
28 Correct 5 ms 10844 KB Output is correct
29 Correct 5 ms 10844 KB Output is correct
30 Correct 5 ms 11188 KB Output is correct
31 Correct 6 ms 10844 KB Output is correct
32 Correct 5 ms 11100 KB Output is correct
33 Correct 5 ms 11100 KB Output is correct
34 Correct 4 ms 10844 KB Output is correct
35 Correct 4 ms 10844 KB Output is correct
36 Correct 4 ms 11032 KB Output is correct
37 Correct 5 ms 10844 KB Output is correct
38 Correct 4 ms 11100 KB Output is correct
39 Correct 235 ms 25396 KB Output is correct
40 Correct 230 ms 25048 KB Output is correct
41 Correct 221 ms 25252 KB Output is correct
42 Correct 219 ms 25480 KB Output is correct
43 Correct 218 ms 25556 KB Output is correct
44 Correct 217 ms 25560 KB Output is correct
45 Correct 393 ms 29576 KB Output is correct
46 Correct 294 ms 32520 KB Output is correct
47 Correct 155 ms 25284 KB Output is correct
48 Correct 124 ms 25884 KB Output is correct
49 Correct 199 ms 25736 KB Output is correct
50 Correct 160 ms 25936 KB Output is correct
51 Correct 202 ms 29156 KB Output is correct