Submission #612530

#	Time	Username	Problem	Language	Result	Execution time	Memory
612530		AugustinasJucas	Fun Tour (APIO20_fun)	C++14	0 / 100	2 ms	2660 KiB

fun

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

const int dydis = 1e5 + 10;

vector<int> gr[dydis];
int n;
bool rem[dydis] = {};
int dst[dydis] = {};
void dfs(int v, int came) {
    if(rem[v]) return;

    for(auto x : gr[v]) {
        if(x == came) continue;
        dst[x] = dst[v] + 1;
        //cout << "dst[" << v << "] = " << dst[v] << ", tai dst[" << x << "] = " << dst[x] << endl;
        dfs(x, v);
    }
}
int furthest (int a) {
    dst[a] = 0;
    dfs(a, -1);
    int mx = 0; int sk = a;
    for(int i = 0; i < n; i++) {
        if(rem[i]) continue;
        //cout << "dst[" << i << "] = " << dst[i] << endl;
        if(dst[i] > mx) {
            mx = dst[i];
            sk = i;
        }
    }
    return sk;
}
vector<int> createFunTour(int N, int Q) {
    n = N;

    for(int i = 0; i < n; i++) {
        for(int j = i+1; j < n; j++) {
            if(hoursRequired(i, j) == 1) {
                gr[i].push_back(j);
                gr[j].push_back(i);
            }
        }
    }

    vector<int> ret;
    int v = furthest(0);
    for(int i = 0; i < n; i++) {
        //cout << "i = " << i << ", v = " << v << endl;
        ret.push_back(v);

        v = furthest(v);
        rem[v] = 1;
    }

    return ret;
}

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