Submission #411853

#	Time	Username	Problem	Language	Result	Execution time	Memory
411853		Ruxandra985	Village (BOI20_village)	C++14	50 / 100	87 ms	14432 KiB

Village

#include <bits/stdc++.h>
#define DIMN 100010
using namespace std;
int mini , maxi;
int which[DIMN];
vector <int> v[DIMN];

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

    for (i = 0 ; i < v[nod].size() ; i++){
        vecin = v[nod][i];
        if (vecin != tt)
            dfs (vecin , 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;

                }
            }
        }

    }

}

int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , x , y , i;
    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?
    }

    dfs (1 , 0);

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

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

    fprintf (fout,"\n");

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

    return 0;
}

Compilation message (stderr)

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

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