CSES - Datatähti Open 2021 - Results
Submission details
Task:Distances
Sender:MKopchev
Submission time:2021-01-29 19:06:32 +0200
Language:C++11
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED29
#2ACCEPTED71
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2details
#2ACCEPTED0.02 s2details

Compiler report

input/code.cpp: In function 'void solve()':
input/code.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
input/code.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i",&u,&v);
         ~~~~~^~~~~~~~~~~~~~
input/code.cpp: In function 'int main()':
input/code.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&t);
     ~~~~~^~~~~~~~~

Code

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

const int nmax=1e2+42;

int n;
vector<int> adj[nmax];

int dst[nmax][nmax];

void dfs(int root,int node,int parent,int d)
{
    dst[root][node]=d;

    for(auto w:adj[node])
        if(w!=parent)
            dfs(root,w,node,d+1);
}

bool used[nmax];

int outp[nmax];

void solve()
{
    scanf("%i",&n);

    for(int i=1;i<=n;i++)adj[i]={};

    for(int i=1;i<n;i++)
    {
        int u,v;

        scanf("%i%i",&u,&v);

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for(int i=1;i<=n;i++)
        dfs(i,i,0,0);

    for(int i=1;i<=n;i++)used[i]=0;

    outp[1]=1;
    used[1]=1;

    int cur=1;

    for(int i=2;i<=n;i++)
    {
        int nxt=-1;

        for(int j=1;j<=n;j++)
            if(used[j]==0&&dst[cur][j]<=3)
            {
                if(nxt==-1)nxt=j;
                else if(dst[1][nxt]<dst[1][j])nxt=j;
                else if(dst[1][nxt]==dst[1][j]&&dst[cur][nxt]>dst[cur][j])nxt=j;
            }

        //cout<<i<<" -> "<<nxt<<endl;

        assert(nxt!=-1);

        used[nxt]=1;
        outp[i]=nxt;

        cur=nxt;
    }

    for(int i=1;i<=n;i++)
        printf("%i ",outp[i]);
    printf("\n");
}

int main()
{
    int t;
    scanf("%i",&t);

    while(t)
    {
        t--;
        solve();
    }

    return 0;
}

Test details

Test 1

Group: 1, 2

Verdict: ACCEPTED

input
100
8
5 2
2 3
3 7
...

correct output
1 8 2 5 6 7 3 4 
1 7 2 8 3 6 4 5 
1 4 6 2 7 5 8 3 
1 8 3 2 4 7 6 5 
1 6 4 7 5 2 3 8 
...

user output
1 3 5 6 2 7 8 4 
1 8 2 7 3 4 6 5 
1 8 7 2 5 6 3 4 
1 3 8 2 4 7 6 5 
1 3 5 2 7 4 8 6 
...

Test 2

Group: 2

Verdict: ACCEPTED

input
100
100
37 59
81 37
44 81
...

correct output
1 99 82 81 59 5 71 55 17 24 13...

user output
1 60 12 11 47 93 19 68 78 81 8...