Submission #1064609

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064609		sammyuri	Fun Tour (APIO20_fun)	C++17	0 / 100	2 ms	2788 KiB

fun

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

const int MAXN = 100005;

vector<int> adj[MAXN];
vector<int> ans, big, small;
int dfs1(int node, int parent) {
    int sz = 1;
    for (auto a : adj[node])
        if (a != parent)
            sz += dfs1(a, node);
    return sz;
}
void dfs2(int node, int parent, int depth, vector<pair<int, int>> &arr) {
    arr.push_back({depth, node});
    for (auto a : adj[node])
        if (a != parent)
            dfs2(a, node, depth + 1, arr);
}
void eradicate(int node) {
    for (auto a : adj[node]) {
        adj[a].erase(find(adj[a].begin(), adj[a].end(), node));
    }
    adj[node].clear();
}


std::vector<int> createFunTour(int N, int Q) {
    int n = N, q = Q;
    for (int i = 1; i < n; i ++) {
        adj[i].push_back((i - 1) / 2);
        adj[(i - 1) / 2].push_back(i);
    }
    int root = 0;
    int rem = n;
    while (rem) {
        // no or only one child - done
        if (adj[root].size() == 0) {
            ans.push_back(root); break;
        } else if (adj[root].size() == 1) {
            ans.push_back(adj[root][0]);
            ans.push_back(root); break;
        }
        // find big and small child
        int big = 0, bigchild = -1;
        for (auto a : adj[root]) {
            int sz = dfs1(a, root);
            if (sz > big) {
                big = sz, bigchild = a;
            }
        }
        int smallchild = adj[root][0];
        if (bigchild == smallchild)
            smallchild = adj[root][1];
        vector<pair<int, int>> nodes_small, nodes_big;
        dfs2(bigchild, root, 0, nodes_big);
        dfs2(smallchild, root, 0, nodes_small);
        sort(nodes_big.begin(), nodes_big.end());
        sort(nodes_small.begin(), nodes_small.end());
        bool bad = false;
        while (nodes_small.size()) {
            auto aa = nodes_small.back(); nodes_small.pop_back();
            auto bb = nodes_big.back(); nodes_big.pop_back();
            eradicate(aa.second); eradicate(bb.second);
            ans.push_back(aa.second);
            ans.push_back(bb.second);
            if (bb.second == bigchild)
                bad = true;
        }
        ans.push_back(root);
        eradicate(root);
        root = bigchild;
        if (bad) break;
    }
    // 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:31:16: warning: unused variable 'q' [-Wunused-variable]
   31 |     int n = N, q = Q;
      |                ^

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