oj.uz

Submission #415983

# Submission time Handle Problem Language Result Execution time Memory
415983 2021-06-01T19:04:55 Z nicolaalexandra Village (BOI20_village) C++14
12 / 100
 11 ms 10880 KB 
#include <bits/stdc++.h>
#define DIM 100010
#define INF 2000000000
using namespace std;

vector <int> L[DIM],w[DIM];
int v[DIM],fth[DIM],sp[DIM],f[DIM],viz[DIM],d[DIM];
int n,i,x,y,sol_min,sol_max,k,idx,poz;


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){
    w[idx].push_back(nod);
    viz[nod] = 1;
    f[nod] = idx;
    for (auto vecin : L[nod])
        if (!viz[vecin])
            dfs2 (vecin,idx);
}

inline int cmp (int a, int b){
    return w[a].size() >= w[b].size();
}

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;
    w[centroid].push_back(centroid);
    d[++k] = centroid;

    int mini = n, poz;
    for (auto vecin : L[centroid]){
        dfs2 (vecin,vecin);

        d[++k] = vecin;
        //cout<<w[vecin].size()<<"\n";
    }


    sort (d+1,d+k+1,cmp);

    for (int poz=2;poz<=k;poz++){

        int i = w[d[poz]].size()-1;
        int j = w[d[poz-1]].size()-1;

        while (i >= 0){

            v[w[d[poz]][i]] = w[d[poz-1]][j];

            i--, j --;
        }

    }

    idx = 2, poz = w[d[2]].size() - 1;

    for (i=1;i<=k;i++){

        for (int j=0;j<w[d[i]].size();j++){

            v[w[d[i]][j]] = w[d[idx]][poz];
            poz--;
            if (poz < 0){
                idx++;
                if (idx > k)
                    idx = 1;
                poz = w[d[idx]].size()-1;
            }
        }

    }

    /*for (i=0;i<w[d[1]].size();i++){
        int x = w[d[1]][i];
        while (f[idx] == d[1] || )
            idx++;
        v[x] = idx++;
    }
*/

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

    /*for (i=1;i<=n;i++)
        if (v[i] == 0)
            cout<<"a";*/

    return 0;
}

Compilation message

Village.cpp: In function 'int main()':
Village.cpp:128:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |         for (int j=0;j<w[d[i]].size();j++){
      |                      ~^~~~~~~~~~~~~~~
Village.cpp:99:9: warning: unused variable 'mini' [-Wunused-variable]
   99 |     int mini = n, poz;
      |         ^~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5324 KB Output is correct
2 Correct 5 ms 5384 KB Output is correct
3 Correct 4 ms 5380 KB Output is correct
4 Correct 4 ms 5324 KB Output is correct
5 Correct 5 ms 5324 KB Output is correct
6 Correct 4 ms 5324 KB Output is correct
7 Correct 4 ms 5324 KB Output is correct
8 Correct 4 ms 5324 KB Output is correct
9 Correct 4 ms 5324 KB Output is correct
10 Correct 4 ms 5324 KB Output is correct
11 Correct 4 ms 5324 KB Output is correct
12 Correct 4 ms 5324 KB Output is correct
13 Correct 5 ms 5324 KB Output is correct
14 Correct 5 ms 5380 KB Output is correct
15 Correct 5 ms 5404 KB Output is correct
16 Correct 4 ms 5324 KB Output is correct
17 Correct 6 ms 5324 KB Output is correct

Subtask #2
0.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5324 KB Output is correct
2 Correct 5 ms 5324 KB Output is correct
3 Correct 5 ms 5384 KB Output is correct
4 Correct 6 ms 5452 KB Output is correct
5 Correct 6 ms 5452 KB Output is correct
6 Correct 5 ms 5452 KB Output is correct
7 Correct 5 ms 5508 KB Output is correct
8 Correct 6 ms 5452 KB Output is correct
9 Correct 5 ms 5452 KB Output is correct
10 Correct 5 ms 5452 KB Output is correct
11 Correct 6 ms 5452 KB Output is correct
12 Runtime error 11 ms 10880 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5324 KB Output is correct
2 Correct 5 ms 5384 KB Output is correct
3 Correct 4 ms 5380 KB Output is correct
4 Correct 4 ms 5324 KB Output is correct
5 Correct 5 ms 5324 KB Output is correct
6 Correct 4 ms 5324 KB Output is correct
7 Correct 4 ms 5324 KB Output is correct
8 Correct 4 ms 5324 KB Output is correct
9 Correct 4 ms 5324 KB Output is correct
10 Correct 4 ms 5324 KB Output is correct
11 Correct 4 ms 5324 KB Output is correct
12 Correct 4 ms 5324 KB Output is correct
13 Correct 5 ms 5324 KB Output is correct
14 Correct 5 ms 5380 KB Output is correct
15 Correct 5 ms 5404 KB Output is correct
16 Correct 4 ms 5324 KB Output is correct
17 Correct 6 ms 5324 KB Output is correct
18 Correct 5 ms 5324 KB Output is correct
19 Correct 5 ms 5324 KB Output is correct
20 Correct 5 ms 5384 KB Output is correct
21 Correct 6 ms 5452 KB Output is correct
22 Correct 6 ms 5452 KB Output is correct
23 Correct 5 ms 5452 KB Output is correct
24 Correct 5 ms 5508 KB Output is correct
25 Correct 6 ms 5452 KB Output is correct
26 Correct 5 ms 5452 KB Output is correct
27 Correct 5 ms 5452 KB Output is correct
28 Correct 6 ms 5452 KB Output is correct
29 Runtime error 11 ms 10880 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -