Submission #982978

#	Time	Username	Problem	Language	Result	Execution time	Memory
982978		ZHIRDILBILDIZ	Fun Tour (APIO20_fun)	C++14	26 / 100	9 ms	1460 KiB

fun

#include <bits/stdc++.h>
#include "fun.h"
#define fi first
#define se second
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>

using namespace std;
const int N = 1e5 + 10;

// int ind[N];
// int ds[N];
// int pw[2 * N];
// pii mn[2 * N][20];

// vector<pii> tr;
// vector<int> gr[N];
// void dfs (int city, int pr) {
//     ind[city] = tr.size();
//     tr.push_back({ds[city], city});
//     for (int i : gr[city]) {
//         if (i == pr)
//             continue;
//         ds[i] = ds[city] + 1;
//         dfs(i, city);
//         tr.push_back({ds[city], city});
//     }
// }

// void build_sparce () {
//     for (int i = 2; i <= tr.size(); ++i)
//         pw[i] = pw[i >> 1] + 1;
//     for (int i = 0; i < tr.size(); ++i)
//         mn[i][0] = tr[i];
//     for (int i = 1; i < 20; ++i)
//         for (int j = 0; j <= (int)tr.size() - (1 << i); ++j)
//             mn[j][i] = min(mn[j][i - 1], mn[j + (1 << (i - 1))][i - 1]);
// }
// int get_lca (int u, int v) {
//     u = ind[u];
//     v = ind[v];
//     if (u > v)
//         swap(u, v);
//     int x = pw[v - u + 1];
//     return min(mn[u][x], mn[v - (1 << x) + 1][x]).se;
// }
// int get_dist (int u, int v) {
//     int lc = get_lca(u, v);
//     return dist[u] + dist[v] - dist[lc] * 2;
// }
// int hoursRequired (int u, int v) {
//     cout << "? " << u << ' ' << v << '\n';
//     int x = get_dist(u, v);
//     return x;
// }
// int attractionsBehind () {
// }

vector<int> createFunTour (int n, int q) {
    vector<int> res;
    if (n <= 500) {
        int dist[n][n];
        int mx = 0;
        pii fr;

        for (int i = 0; i < n; ++i) {
            dist[i][i] = 0;
            for (int j = i + 1; j < n; ++j) {
                if (i != j) {
                    int w = hoursRequired(i, j);
                    dist[i][j] = w;
                    dist[j][i] = w;
                }
                mx = max(mx, dist[i][j]);
                if (mx == dist[i][j])
                    fr = {i, j};
            }
        }
        bool us[n] = {};
        us[fr.fi] = 1;
        res.push_back(fr.fi);
        us[fr.se] = 1;
        res.push_back(fr.se);
        
        int city = fr.se;
        for (int i = 3; i <= n; ++i) {
            int loc_mx = 0;
            int who = -1;
            for (int j = 0; j < n; ++j) {
                if (us[j])
                    continue;
                loc_mx = max(loc_mx, dist[city][j]);
                if (loc_mx == dist[city][j])
                    who = j;
            }
            us[who] = 1;
            res.push_back(who);
            city = who;
        }
    }
    return res;
}

// signed main () {

//     int n, q;
//     cin >> n >> q;
//     for (int i = 1; i < n; ++i) {
//         int u, v;
//         cin >> u >> v;
//         gr[u].push_back(v);
//         gr[v].push_back(u);
//     }

//     dfs(0, -1);
//     build_sparce();

//     vector<int> ans = createFunTour(n, q);
//     for (int i : ans)
//         cout << i << ' ';
//     cout << '\n';

//     return 0;
// }

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