Submission #1064785

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064785		sammyuri	Fun Tour (APIO20_fun)	C++17	47 / 100	78 ms	20944 KiB

fun

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

const int MAXN = 100005;

vector<int> adj[MAXN];
int par[MAXN];
pair<int, int> deepest[MAXN];
bool dead[MAXN];
// returns {fardepth, farnode}
pair<int, int> dfs1(int node, int parent) {
    pair<int, int> ans = {0, node};
    for (auto a : adj[node])
        if (a != parent) {
            pair<int, int> xx = dfs1(a, node);
            xx.first ++;
            ans = max(ans, xx);
        }
    deepest[node] = ans;
    return ans;
}
pair<int, int> furthest(int node, int prev) {
    pair<int, int> ans = {0, node};
    for (auto a : adj[node])
        if (a != prev && a != par[node])
            ans = max(ans, deepest[a]);
    if (par[node] != -1 && !dead[par[node]]) {
        pair<int, int> xx = furthest(par[node], node);
        xx.first ++;
        ans = max(ans, xx);
    }
    return ans;
}

int root = 0;
void uproot(int node) {
    pair<int, int> ans = {0, node};
    for (auto a : adj[node])
        if (a != par[node]) {
            pair<int, int> xx = deepest[a];
            xx.first ++;
            ans = max(ans, xx);
        }
    deepest[node] = ans;
    if (par[node] != -1 && !dead[par[node]])
        uproot(par[node]);
}
void eradicate(int node) {
    dead[node] = true;
    for (auto a : adj[node]) {
        adj[a].erase(find(adj[a].begin(), adj[a].end(), node));
    }
    adj[node].clear();
    if (par[node] != -1 && !dead[par[node]])
        uproot(par[node]);
}

void eradicate2(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> furthest2(int node, int parent, int depth) {
    pair<int, int> ans = {depth, node};
    for (auto a : adj[node])
        if (a != parent)
            ans = max(ans, furthest2(a, node, depth + 1));
    return ans;
}


std::vector<int> createFunTour(int N, int Q) {
    int n = N, q = Q;
    if (n > 500) {
        // we know it is a binary tree
        memset(dead, false, sizeof(dead));
        par[0] = -1;
        for (int i = 1; i < n; i ++) {
            adj[i].push_back((i - 1) / 2);
            adj[(i - 1) / 2].push_back(i);
            par[i] = (i - 1) / 2;
        }
        dfs1(0, -1);
        pair<int, int> cur = deepest[0];
        vector<int> ans;
        for (int tt = 0; tt < n - 1; tt ++) {
            int prev = cur.second;
            cur = furthest(prev, -1);
            ans.push_back(prev);
            eradicate(prev);
            // cout << cur.first << " " << cur.second << endl;
        }
        ans.push_back(cur.second);
        return ans;

    } else {
        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 = furthest2(cur.second, -1, 0);
        cur = furthest2(cur.second, -1, 0);
        cur = furthest2(cur.second, -1, 0);
        vector<int> ans;
        for (int tt = 0; tt < n - 1; tt ++) {
            int prev = cur.second;
            cur = furthest2(prev, -1, 0);
            ans.push_back(prev);
            eradicate2(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:77:16: warning: unused variable 'q' [-Wunused-variable]
   77 |     int n = N, q = Q;
      |                ^

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