Submission #915193

#	Time	Username	Problem	Language	Result	Execution time	Memory
915193		3as8	Village (BOI20_village)	C++14	56 / 100	101 ms	15208 KiB

Village

#include <bits/stdc++.h>

#define ll long long
#define endl "\n"
#define fastIO cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false);

#define mid ((l + r) / 2)
#define lChild ((index * 2) + 1)
#define rChild ((index * 2) + 2)

using namespace std;

ll ans = 0;
bool dfs(vector<vector<ll> >& graph, vector<ll>& cur, ll startIndex, ll p) {

    bool hasLeaf = false;
    bool isLeaf = true;
    for(auto el : graph[startIndex]) {
        if(el == p) continue;

        hasLeaf &= dfs(graph, cur, el, startIndex);

        isLeaf = false;

    }

    if(isLeaf && cur[startIndex] == startIndex ) {

        ans += 2;
        //cout<<"swap "<<cur[p] + 1<<" "<<cur[startIndex] + 1<<endl;

        swap(cur[p], cur[startIndex]);

        return isLeaf;
    }

    if(cur[startIndex] == startIndex && p != startIndex) {


        ans += 2;
       // cout<<"swap no leaf "<<cur[p] + 1<<" "<<cur[startIndex] + 1<<endl;

        swap(cur[p], cur[startIndex]);
    }

    return isLeaf;
}


void deez(vector<vector<ll> >& graph, vector<ll>& dist, ll startIndex, ll p, ll depth = 0) {

    dist[startIndex] = depth;
    for(auto el : graph[startIndex]) {
        if(el == p) continue;

        deez(graph, dist, el, startIndex, depth + 1);
    }
}

void solve(ll _) {

    ll n; cin>>n;

    vector<vector<ll> > graph(n);
    for(int i = 0; i < n - 1; i++) {
        ll x, y; cin>>x>>y;
        x--; y--;

        graph[x].push_back(y);
        graph[y].push_back(x);
    }


    if(n <= 10) {

        vector<vector<ll> > dist(n, vector<ll>(n, -1));

        for(int i = 0; i < n; i++) {
            deez(graph, dist[i], i, -1);

        }


        vector<ll> arr(n);
        for(int i = 0; i < n; i++) arr[i] = i;

        vector<ll> mnA, mxA;

        ll mn = LLONG_MAX, mx = LLONG_MIN;
        do {

            bool is = true;
            for(int i = 0; i < n; i++) {
                is &= (arr[i] != i);
            }

            if(!is) continue;

            ll d = 0;
            for(int i = 0; i < n; i++) {
                d += dist[i][arr[i]];
            }

            if(mn > d) {
                mnA = arr;
            }
            if(mx < d) {
                mxA = arr;
            }

            mn = min(mn, d);
            mx = max(mx, d);

        } while(next_permutation(arr.begin(), arr.end()));


        cout<<mn<<" "<<mx<<endl;
        for(auto el : mnA) cout<<el + 1<<" ";
        cout<<endl;

        for(auto el : mxA) cout<<el + 1<<" ";
        cout<<endl;

        return;

    }
    vector<bool> stat(n, true);
    vector<ll> curr(n);
    for(int i = 0; i < n; i++) curr[i] = i;

    dfs(graph, curr, 0, 0);

    for(int i = 0; i < n; i++) {

        if(curr[i] == i) {
            ans += 2;
            swap(curr[i], curr[graph[i][0]]);

        }

    }

    cout<<ans<<" "<<2<<endl;
    for(auto el : curr) cout<<el + 1<<" ";
    cout<<endl;

    for(auto el : curr) cout<<el + 1<<" ";
    cout<<endl;
}

int main() {


    //freopen("file.in", "r", stdin);
    //freopen("file.out", "w", stdout);

    ll t = 0; solve(t);
}

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