Submission #411921

#	Time	Username	Problem	Language	Result	Execution time	Memory
411921		Ruxandra985	Village (BOI20_village)	C++14	56 / 100	156 ms	18872 KiB

Village

#include <bits/stdc++.h>
#define DIMN 100010
using namespace std;
int n , mini , maxi , fth , centroid;
int which[DIMN] , wm[DIMN] , sub[DIMN] , f[DIMN];
vector <int> v[DIMN] , w[DIMN];

void dfs (int nod , int tt){
    int i , vecin , ok = 1;



    for (i = 0 ; i < v[nod].size() ; i++){
        vecin = v[nod][i];
        if (vecin != tt){
            dfs (vecin , nod);
            sub[nod] += sub[vecin] + 1;

            if (sub[vecin] + 1 > n / 2)
                ok = 0;

        }
    }

    if (n - sub[nod] - 1 > n / 2)
        ok = 0;

    if (ok && !centroid){
        centroid = nod;
        fth = tt;
    }

    maxi = maxi + 2 * min(sub[nod] + 1 , n - 1 - sub[nod]);

    if (which[nod] == nod){ /// nu l ai schimbat inca

        if (tt){
            swap(which[nod] , which[tt]);
            mini += 2;
        }
        else {
            for (i = 0 ; i < v[nod].size() ; i++){
                vecin = v[nod][i];
                if (vecin != tt){

                    swap(which[vecin] , which[nod]);
                    mini += 2;
                    break;

                }
            }
        }

    }

}

void dfs2 (int nod , int poz){
    int i , vecin;

    f[nod] = 1;

    w[poz].push_back(nod);

    for (i = 0 ; i < v[nod].size() ; i++){
        vecin = v[nod][i];
        if (!f[vecin]){

            if (nod == centroid)
                poz++;

            dfs2 (vecin , poz);

        }
    }
}

int cmp (vector <int> a , vector <int> b){
    return a.size() > b.size();
}


int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int x , y , i , a , b , elem;
    fscanf (fin,"%d",&n);
    for (i = 1 ; i < n ; i++){
        fscanf (fin,"%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }

    /// solve pentru minim

    mini = 0;

    for (i = 1 ; i <= n ; i++){
        which[i] = i; /// ce nod e acum in locul in care se afla nodul i?
        wm[i] = i;
    }

    dfs (1 , 0);

    fprintf (fout,"%d %d\n" , mini , maxi);

    for (i = 1 ; i <= n ; i++)
        fprintf (fout,"%d ",which[i]);

    fprintf (fout,"\n");

    dfs2 (centroid , 1);

    a = 1;
    b = 2;

    elem = v[centroid].size();

    swap(w[1] , w[elem + 1]);

    sort (w + 1 , w + elem + 1 , cmp);

    while (a != b && a <= elem && b <= elem){

        swap(wm[w[a].back()] , wm[w[b].back()]);
        w[a].pop_back();
        w[b].pop_back();

        if (w[a].empty()){
            while (a <= elem){

                if (!w[a].empty())
                    break;

                a++;
            }

            if (a > elem)
                break;
        }

        b = max(b , a + 1);

        while (b <= elem){

            if (!w[b].empty())
                break;

            b++;
        }

        if (b > elem)
            break;

    }

    /// momentan ai pus tot ce era de pus

    int ok = 1;

    for (i = 1 ; i <= elem ; i++){
        if (!w[i].empty()){
            ok = 0;
            swap(wm[centroid] , wm[w[i][0]]);
            break;
        }
    }


    if (ok){
        if (centroid == 1){
            swap(wm[centroid] , wm[2]);
        }
        else swap(wm[centroid] , wm[centroid - 1]);
    }

    for (i = 1 ; i <= n ; i++)
        fprintf (fout,"%d ",wm[i]);

    return 0;
}

Compilation message (stderr)

Village.cpp: In function 'void dfs(int, int)':
Village.cpp:13:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for (i = 0 ; i < v[nod].size() ; i++){
      |                  ~~^~~~~~~~~~~~~~~
Village.cpp:42:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |             for (i = 0 ; i < v[nod].size() ; i++){
      |                          ~~^~~~~~~~~~~~~~~
Village.cpp: In function 'void dfs2(int, int)':
Village.cpp:65:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for (i = 0 ; i < v[nod].size() ; i++){
      |                  ~~^~~~~~~~~~~~~~~
Village.cpp: In function 'int main()':
Village.cpp:88:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |     fscanf (fin,"%d",&n);
      |     ~~~~~~~^~~~~~~~~~~~~
Village.cpp:90:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |         fscanf (fin,"%d%d",&x,&y);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 19 / 38
• Subtask 3: 25 / 50