Submission #1313543

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313543		cleimek	Village (BOI20_village)	C++20	12 / 100	1095 ms	568 KiB

Village

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e8;
vector<vector<int>> graph;

void DFS(int v, int prev, vector<int>& dist){
    dist[v]=dist[prev]+1;
    for(auto u : graph[v]){
        if(u == prev) continue;
        DFS(u,v,dist);
    }
}

bool Check(vector<int>& arr){
    for(int i=0; i<arr.size(); ++i){
        if(arr[i]==i+1) return false;
    }
    return true;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    graph.resize(n+1);
    for(int i=1; i<n; ++i){
        int nodeA, nodeB;
        cin >> nodeA >> nodeB;
        graph[nodeA].push_back(nodeB);
        graph[nodeB].push_back(nodeA);
    }

    vector<vector<int>> dist(n+1,vector<int>(n+1,-1));
    for(int i=1; i<=n; ++i){
        DFS(i,0,dist[i]);
    }

    vector<int> perm;
    for(int i=1; i<=n; ++i) perm.push_back(i);

    int ansMin=INF;
    int ansMax=-INF;
    vector<int> minOrder(n,1);
    vector<int> maxOrder(n,1);

    do{
        //check
        if(!Check(perm)) continue;

        int res=0;
        for(int i=0; i<n; ++i){
            res += dist[i+1][perm[i]];
        }

        if(ansMin > res){
            ansMin=res;
            minOrder=perm;
        }

        if(ansMax < res){
            ansMax=res;
            maxOrder=perm;
        }

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

    cout << ansMin << " " << ansMax << "\n";
    for(auto a : minOrder) cout << a << " ";
    cout << "\n";
    for(auto a : maxOrder) cout << a << " ";
    cout << '\n';


    
    return 0;
}

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