Submission #342912

#	Time	Username	Problem	Language	Result	Execution time	Memory
342912		urd05	Village (BOI20_village)	C++14	12 / 100	49 ms	500 KiB

Village

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

int dist[10][10];
const int INF=10000;
vector<int> small(10);
vector<int> big(10);

int main(void) {
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++) {
        for(int j=0;j<n;j++) {
            dist[i][j]=INF;
        }
        dist[i][i]=0;
    }
    for(int i=1;i<n;i++) {
        int u,v;
        scanf("%d %d",&u,&v);
        u--;
        v--;
        dist[u][v]=1;
        dist[v][u]=1;
    }
    for(int k=0;k<n;k++) {
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
            }
        }
    }
    vector<int> v;
    for(int i=0;i<n;i++) {
        v.push_back(i);
    }
    int val=1;
    for(int i=1;i<=n;i++) {
        val*=i;
    }
    int mini=INF;
    int maxi=-INF;
    for(int i=0;i<val;i++) {
        int sum=0;
        next_permutation(v.begin(),v.end());
        bool flag=true;
        for(int j=0;j<n;j++) {
            if (v[j]==j) {
                flag=false;
                break;
            }
            sum+=dist[j][v[j]];
        }
        if (!flag) {
            continue;
        }
        if (sum<mini) {
            mini=sum;
            for(int j=0;j<n;j++) {
                small[j]=v[j];
            }
        }
        if (sum>maxi) {
            maxi=sum;
            for(int j=0;j<n;j++) {
                big[j]=v[j];
            }
        }
    }
    printf("%d %d\n",mini,maxi);
    for(int i=0;i<n;i++) {
        printf("%d ",small[i]+1);
    }
    printf("\n");
    for(int i=0;i<n;i++) {
        printf("%d ",big[i]+1);
    }
}

Compilation message (stderr)

Village.cpp: In function 'int main()':
Village.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   11 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
Village.cpp:20:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   20 |         scanf("%d %d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~

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