Submission #395198

#	Time	Username	Problem	Language	Result	Execution time	Memory
395198		abc864197532	Fun Tour (APIO20_fun)	C++17	26 / 100	128 ms	14656 KiB

fun

#include <bits/stdc++.h>
// #include "grader_fun.cpp"
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define test(x) cout << "Line(" << __LINE__ << ") " #x << ' ' << x << endl
#define printv(x) {\
	for (auto i : x) cout << i << ' ';\
	cout << endl;\
}
#define pii pair <int, int>
#define pll pair <lli, lli>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
template<typename A, typename B>
ostream& operator << (ostream& o, pair<A, B> a){
    return o << a.X << ' ' << a.Y;
}
template<typename A, typename B>
istream& operator >> (istream& o, pair<A, B> &a){
    return o >> a.X >> a.Y;
}

int hoursRequired(int u, int v);

vector <int> createFunTour(int n, int q) {
    vector <bool> vis(n, false);
    vector <int> ans;
    auto get_dia = [&](int s) {
        int cur = -1, dis = -1;
        for (int i = 0; i < n; ++i) if (!vis[i]) {
            int tmp = hoursRequired(s, i);
            if (cur == -1 || dis < tmp) cur = i, dis = tmp;
        }
        return cur;
    };
    int v = get_dia(0);
    ans.pb(v);
    vis[v] = true;
    for (int i = 0; i < n - 1; ++i) {
        v = get_dia(v);
        ans.pb(v);
        vis[v] = true;
    }
    return ans;
}

/*
7 400000
0 1
0 5
0 6
1 2
1 4
2 3
 */

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