Submission #411938

#	Time	Username	Problem	Language	Result	Execution time	Memory
411938		Ruxandra985	Village (BOI20_village)	C++14	100 / 100	121 ms	18948 KiB

Village

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

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;


    if (nod != centroid)
        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 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 %lld\n" , mini , maxi);

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

    fprintf (fout,"\n");

    dfs2 (centroid , 0);

    a = 1;
    b = 2;

    elem = v[centroid].size();

    for (i = 1 ; i <= elem ; i++)
        h.push(make_pair(w[i].size() , i));

    while (h.size() >= 2){

        a = h.top().second;
        h.pop();
        b = h.top().second;
        h.pop();

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

        if (w[a].size())
            h.push(make_pair(w[a].size() , a));
        if (w[b].size())
            h.push(make_pair(w[b].size() , b));

    }

    if (h.empty()){
        if (centroid == 1){
            swap(wm[centroid] , wm[2]);
        }
        else swap(wm[centroid] , wm[centroid - 1]);
    }
    else {
        a = h.top().second;
        swap(wm[w[a].back()] , wm[centroid]);
    }

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

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