Submission #414310

#	Time	Username	Problem	Language	Result	Execution time	Memory
414310		ACmachine	Fun Tour (APIO20_fun)	C++17	26 / 100	282 ms	524292 KiB

fun

#include "fun.h"

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

#define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
#define FORD(i, j, k, l) for(int i = (j); i>=(k); i -= (l))
#define REP(i, n) FOR(i, 0, n, 1)
#define REPD(i, n) FORD(i, n, 0, 1)
#define pb push_back
typedef long long ll;
const int INF = (int)1e9;
const ll INFF = (ll)1e18;



std::vector<int> createFunTour(int n, int Q) {
    vector<vector<int>> mat(n, vector<int>(n));
    REP(i, n){
        REP(j, i + 1){
            mat[i][j] = mat[j][i] = hoursRequired(i, j);
        }
    }
    vector<int> ans;
    vector<vector<int>> g(n);
    vector<bool> used(n, false);
    REP(i, n){
        REP(j, n){
            if(mat[i][j] == 1)
                g[i].pb(j);
        }
    }
    vector<int> dist(n, -1);
    function<void(int, int)> dfs = [&](int v, int p){
        if(used[v]) 
            return;
        dist[v] = (p == -1 ? 0 : dist[p] + 1);
        for(int x : g[v]){
            if(x == p) continue;
            dfs(x, v);
        }
    };
    dfs(0, -1);
    int f = max_element(dist.begin(), dist.end()) - dist.begin();
    REP(i, n){
        ans.pb(f);
        fill(dist.begin(), dist.end(), -1);
        dfs(f, -1);
        used[f] = true; 
        f = max_element(dist.begin(), dist.end()) - dist.begin();
    }
    return ans;
}

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