Submission #1072688

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072688		12345678	Fun Tour (APIO20_fun)	C++17	26 / 100	18 ms	600 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=505;

int vs[nx],rt;
vector<int> d[nx], res;
pair<int, int> mx;

void dfs(int u, int p, int w)
{
    mx=max(mx, {w, u});
    for (auto v:d[u]) if (v!=p&&!vs[v]) dfs(v, u, w+1);
}

int find(int x)
{
   mx={-1, 0};
   dfs(x, x, 0);
   return mx.second;
}
std::vector<int> createFunTour(int N, int Q) {
    for (int i=0; i<N; i++) for (int j=i+1; j<N; j++) if (hoursRequired(i, j)==1) d[i].push_back(j), d[j].push_back(i);
    rt=find(0);
    res.push_back(rt);
    vs[rt]=1;
    for (int i=1; i<N; i++) rt=find(rt), vs[rt]=1, res.push_back(rt);
    return res;
}

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 34