Submission #1064894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064894		sammyuri	Fun Tour (APIO20_fun)	C++17	66 / 100	112 ms	22056 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]) {
            pair<int, int> xx = deepest[a];
            xx.first ++;
            ans = max(ans, xx);
        }
    if (par[node] != -1 && !dead[par[node]]) {
        pair<int, int> xx = furthest(par[node], node);
        xx.first ++;
        ans = max(ans, xx);
    }
    return ans;
}

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;
}
void dfs2(int node, int parent) {
    par[node] = parent;
    for (auto a : adj[node])
        if (a != parent)
            dfs2(a, node);
}

int root = 0;
int n, q;

std::vector<int> createFunTour(int N, int Q) {
    n = N, q = Q;
    if (n > 500) {
        // we know it is a binary tree
        // if 0 is connected to 1 and 2, use this solution
        if (hoursRequired(0, 1) == 1 && hoursRequired(0, 2) == 1) {
            root = 0;
            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;
            }
        }
        // otherwise build the tree
        else {
            // get distances to each node
            vector<pair<bool, pair<int, int>>> spine;
            spine.push_back({false, {0, 0}});
            for (int i = 1; i < n; i ++) {
                int dist = hoursRequired(0, i);
                // bigger - attach it
                while (spine.back().second.first > dist) {
                    if (spine.back().first == false) {
                        int a = spine.back().second.second, b = i;
                        // cout << a << " " << b << endl;
                        adj[a].push_back(b); adj[b].push_back(a);
                    }
                    spine.pop_back();
                }
                // equal - replace it
                if (spine.back().second.first == dist) {
                    spine.pop_back();
                }
                bool attached = false;
                // one smaller - attach it
                if (spine.back().second.first == dist - 1) {
                    attached = true;
                    int a = spine.back().second.second, b = i;
                    // cout << a << " " << b << endl;
                    adj[a].push_back(b); adj[b].push_back(a);
                }
                spine.push_back({attached, {dist, i}});
            }
            root = spine.back().second.second;
            dfs2(root, -1);
            // for (int i = 0; i < n; i ++)
            //     cout << par[i] << " "; cout << endl;
        }
        memset(dead, false, sizeof(dead));
        dfs1(root, -1);
        pair<int, int> cur = deepest[root];
        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;
        }
    
        // for (auto a : ans)
        //     cout << a << " "; cout << 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);
        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

10 100000
0 1 1 2 1 3 3 4 4 5 3 6 6 8 7 8 8 9
*/

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