oj.uz

Submission #415938

# Submission time Handle Problem Language Result Execution time Memory
415938 2021-06-01T17:49:59 Z nicolaalexandra Village (BOI20_village) C++14
0 / 100
 700 ms 5324 KB 
#include <bits/stdc++.h>
#define DIM 100010
#define INF 2000000000
using namespace std;

vector <int> L[DIM],w[DIM],aux;
set <int> s;
int v[DIM],fth[DIM],sp[DIM],f[DIM],viz[DIM];
int n,i,x,y,sol_min,sol_max;


void dfs (int nod, int tata){
    fth[nod] = tata;
    sp[nod] = 1;
    for (auto vecin : L[nod])
        if (vecin != tata){
            dfs (vecin,nod);
            sp[nod] += sp[vecin];
        }

    if (nod != 1 && v[nod] == nod){

        sol_min += 2;
        swap (v[nod],v[fth[nod]]);

    }

    sol_max += 2 * min (sp[nod],n-sp[nod]);

}

int get_centroid (int nod, int tata){

    int maxim = 0, heavy_son = 0;
    for (auto vecin : L[nod]){
        if (vecin == tata)
            continue;
        if (sp[vecin] > maxim)
            maxim = sp[vecin], heavy_son = vecin;
    }

    if (maxim <= n/2 && n - sp[nod] <= n/2)
        return nod;
    else return get_centroid(heavy_son,nod);

}


void dfs2 (int nod, int idx){
    s.insert(nod);
    w[idx].push_back(nod);
    viz[nod] = 1;
    for (auto vecin : L[nod])
        if (!viz[vecin])
            dfs2 (vecin,idx);
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n;
    for (i=1;i<n;i++){
        cin>>x>>y;
        L[x].push_back(y);
        L[y].push_back(x);
    }

    for (i=1;i<=n;i++)
        v[i] = i;

    dfs (1,0);

    for (i=1;i<=n;i++)
        if (v[i] == i){
            sol_min += 2;
            if (i != 1)
                swap (v[i],v[fth[i]]);
            else swap (v[i],v[L[1][0]]);
        }

    cout<<sol_min<<" "<<sol_max<<"\n";
    for (i=1;i<=n;i++)
        cout<<v[i]<<" ";

    cout<<"\n";

    memset (v,0,sizeof v);
    int centroid = get_centroid(1,0);

    viz[centroid] = 1;
    for (auto vecin : L[centroid])
        dfs2 (vecin,vecin);

    s.insert(centroid);
    for (auto vecin : L[centroid]){

        /// mai intai scot din set elemente care se afla in subarborele lui vecin
        aux.clear();
        for (auto it : w[vecin]){
            if (s.find(it) != s.end())
                aux.push_back(it); /// dupa trb sa le adaug la loc
            s.erase(it);
        }

        for (auto it : w[vecin]){
            v[it] = *s.begin();
            s.erase(s.begin());
        }


        for (auto it : aux)
            s.insert(it);
    }

    /// unde duc centroidul?
    for (i=1;i<=n;i++)
        f[v[i]]++;
    for (i=1;i<=n;i++)
        if (!f[i]){
            v[centroid] = i;
            break;
        }

    for (i=1;i<=n;i++)
        cout<<v[i]<<" ";


    return 0;
}

Subtask #1
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1081 ms 5324 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 38.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1081 ms 5324 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1081 ms 5324 KB Time limit exceeded
2 Halted 0 ms 0 KB -