Submission #1064782

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064782		sammyuri	Fun Tour (APIO20_fun)	C++17	21 / 100	94 ms	21952 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]);
}



std::vector<int> createFunTour(int N, int Q) {
    int n = N, q = Q;
    // 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);

    // 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 = 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);

    // 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:62:16: warning: unused variable 'q' [-Wunused-variable]
   62 |     int n = N, q = Q;
      |                ^

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