Submission #386118

#	Time	Username	Problem	Language	Result	Execution time	Memory
386118		phathnv	Fun Tour (APIO20_fun)	C++11	0 / 100	2 ms	492 KiB

fun

#include <bits/stdc++.h>
#include "fun.h"

using namespace std;

vector<int> createFunTour(int N, int Q) {
    pair<int, int> best = {N, 0};
    for(int i = 0; i < N; i++){
        int x = attractionsBehind(0, i);
        if (x >= (N + 1) / 2)
            best = min(best, {x, i});
    }
    int centroid = best.second;

    vector<int> subtreeRoots, distToCentroid(N);
    for(int i = 0; i < N; i++){
        distToCentroid[i] = hoursRequired(centroid, i);
        if (distToCentroid[i] == 1)
            subtreeRoots.push_back(i);
    }
    vector<vector<pair<int, int>>> subtree(3);
    for(int i = 0; i < N; i++){
        if (i == centroid)
            continue;
        for(int j = 0; j < (int) subtreeRoots.size(); j++)
            if (j + 1 == (int) subtreeRoots.size())
                subtree[j].push_back({distToCentroid[i], i});
            else if (hoursRequired(subtreeRoots[j], i) == distToCentroid[i] - 1){
                subtree[j].push_back({distToCentroid[i], i});
                break;
            }
    }
    for(auto &v : subtree)
        sort(v.begin(), v.end());

    vector<int> answer;
    int lastSubtree = -1;
    while (true){
        int sum = 0, maxSz = -1, big = -1;
        pair<int, int> nxt = {-1, -1};

        for(int i = 0; i < 3; i++){
            sum += subtree[i].size();
            if (maxSz < (int) subtree[i].size()){
                big = i;
                maxSz = subtree[i].size();
            }
            if (i != lastSubtree && i < (int) subtreeRoots.size())
                nxt = max(nxt, {subtree[i].back().first, i});
        }
        if (sum == 0)
            break;
        int nxtSubtree = nxt.second;
        if (sum >= 2 * maxSz && lastSubtree != big){
            cerr << "merge " << endl;
            cerr << lastSubtree << ' ' << nxtSubtree << endl;
            for(const auto &v : subtree){
                for(auto p : v)
                    cerr << p.first << ',' << p.second << ' ';
                cerr << endl;
            }

            vector<int> small;
            for(int i = 0; i < 3; i++)
                if (i != big)
                    small.push_back(i);
            for(auto p : subtree[small[1]])
                subtree[small[0]].push_back(p);
            sort(subtree[small[0]].begin(), subtree[small[0]].end());
            if (lastSubtree != -1 && lastSubtree != big){
                int oth = (lastSubtree != small[0]);
                if (!subtree[oth].empty() && distToCentroid[answer.back()] < subtree[oth].back().first)
                    swap(subtree[small[0]], subtree[big]);
            }
            assert(subtree[small[0]].size() == subtree[big].size());
            while (!subtree[small[0]].empty()){
                answer.push_back(subtree[big].back().second);
                answer.push_back(subtree[small[0]].back().second);
                subtree[big].pop_back();
                subtree[small[0]].pop_back();
            }
            break;
        } else {
            lastSubtree = nxtSubtree;
            answer.push_back(subtree[lastSubtree].back().second);
            subtree[lastSubtree].pop_back();
        }
    }

    answer.push_back(centroid);
    cerr << "answer: ";
    for(int x : answer)
        cerr << x << ' ';
    cerr << endl;
    return answer;
}

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