Submission #415844

#	Time	Username	Problem	Language	Result	Execution time	Memory
415844		nicolaalexandra	Village (BOI20_village)	C++14	50 / 100	167 ms	15020 KiB

Village

#include <bits/stdc++.h>
#define DIM 100010
#define INF 2000000000
using namespace std;

vector <int> L[DIM];
int v[DIM],fth[DIM];
int n,i,x,y,sol_min;


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

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

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

    }

}


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<<" "<<0<<"\n";
    for (i=1;i<=n;i++)
        cout<<v[i]<<" ";

    cout<<"\n";

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


    return 0;
}

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