Submission #1064741

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064741		sammyuri	Fun Tour (APIO20_fun)	C++17	26 / 100	70 ms	17244 KiB

fun

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

const int MAXN = 100005;

vector<int> adj[MAXN];

void eradicate(int node) {
    for (auto a : adj[node]) {
        adj[a].erase(find(adj[a].begin(), adj[a].end(), node));
    }
    adj[node].clear();
}

// returns {fardepth, farnode}
pair<int, int> furthest(int node, int parent, int depth) {
    pair<int, int> ans = {depth, node};
    for (auto a : adj[node])
        if (a != parent)
            ans = max(ans, furthest(a, node, depth + 1));
    return ans;
}


std::vector<int> createFunTour(int N, int Q) {
    int n = N, q = Q;
    // find out graph
    for (int i = 0; i < n - 1; i ++) {
        for (int j = i + 1; j < n; j ++) {
            if (hoursRequired(i, j) == 1)
                adj[i].push_back(j), adj[j].push_back(i);
        }
    }
    // find any leaf node
    pair<int, int> cur = {0, 0};
    cur = furthest(cur.second, -1, 0);
    cur = furthest(cur.second, -1, 0);
    cur = furthest(cur.second, -1, 0);
    vector<int> ans;
    for (int tt = 0; tt < n - 1; tt ++) {
        int prev = cur.second;
        cur = furthest(prev, -1, 0);
        ans.push_back(prev);
        eradicate(prev);
    }
    ans.push_back(cur.second);

    // for (auto a : ans)
    //     cout << a << " "; cout << endl;
    return ans;
}

/*
13 1000 
0 1 0 2
1 3 1 4
2 5 2 6
3 7 3 8
4 9 4 10
5 11 5 12
*/

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:27:16: warning: unused variable 'q' [-Wunused-variable]
   27 |     int n = N, q = Q;
      |                ^

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