Submission #404817

# Submission time Handle Problem Language Result Execution time Memory
404817 2021-05-15T05:19:19 Z dvdg6566 Ancient Machine (JOI21_ancient_machine) C++17
Compilation error
0 ms 0 KB
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
typedef vector<ll> vi;
typedef vector<pi> vpi;
#define pb emplace_back
#define f first 
#define s second
#define mp make_pair
#define SZ(x) (ll)x.size()
#define ALL(x) x.begin(),x.end()
#define lb lower_bound
#define ub upper_bound

const ll MAXN=5010;

ll N,a,b,c,d,Q;
vi V[MAXN];
ll ans;
ll p[MAXN];
ll sub[MAXN];
ll small[MAXN];
ll A[MAXN];
ll out[MAXN];

ll dfs(ll x,ll pa){
    sub[x]=1;
    p[x]=pa;
    for(auto v:V[x])if(v!=pa)sub[x]+=dfs(v,x);
    return sub[x];
}

void dfs2(ll x,ll d,ll pa){
    if(A[x])ans=max(ans,d);
    for(auto v:V[x])if(v!=pa)dfs2(v,d+1,x);
}

int main(){
    cin>>N;
    for(ll i=1;i<N;++i){
        cin>>a>>b;
        V[a].pb(b);
        V[b].pb(a);
    }    
    dfs(1,-1);
    for(ll i=1;i<=N;++i){
        b=N-sub[i];
        for(auto j:V[i])if(j!=p[i]){
            b=max(b,sub[j]);
        }
        small[i]=N-b; // everything except biggest subtree
    }
    // for(ll i=1;i<=N;++i)cerr<<small[i]<<' ';cerr<<'\n';
    vpi nodes;
    for(ll i=1;i<=N;++i)nodes.pb(small[i],i);
    sort(ALL(nodes));

    for(ll i=(N/2)*2; i>=2;i-=2){
        while(SZ(nodes)&&nodes.back().f>=i/2){
            pi t=nodes.back();nodes.pop_back();
            A[t.s]=1;
            // cerr<<"Adding "<<t.s<<'\n';
            dfs2(t.s,1,-1);
        }
        out[i]=ans;
    }
    for(int i=1;i<=N;++i){
        if(i%2)cout<<1<<'\n';
        else cout<<out[i]<<'\n';
    }
}



    

Compilation message

/usr/bin/ld: /tmp/ccaQlngH.o: in function `main':
grader_anna.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccS356lJ.o:Anna.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccaQlngH.o: in function `main':
grader_anna.cpp:(.text.startup+0x14c): undefined reference to `Anna(int, std::vector<char, std::allocator<char> >)'
collect2: error: ld returned 1 exit status

/usr/bin/ld: /tmp/cc0N8BKr.o: in function `main':
grader_bruno.cpp:(.text.startup+0x24d): undefined reference to `Bruno(int, int, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status