Submission #1177402

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177402		anmattroi	Fun Tour (APIO20_fun)	C++17	47 / 100	74 ms	16060 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
#define maxn 100005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;

//hoursRequired(X, Y) //dis X->Y
//attractionsBehind(X, Y) //subtree size of Y if root is X

int centroid, sz[maxn], dist[maxn], nho[maxn];

vector<int> sub1(vector<int> Lis, int N) {
    vector<ii> type1, type2;

    for (int i = 0; i < N; i++) {
        if (i == centroid) continue;
        int dis = hoursRequired(Lis[0], i);
        if (dis + 1 == dist[i]) type1.emplace_back(dist[i], i);
        else type2.emplace_back(dist[i], i);
    }
    sort(type1.begin(), type1.end());
    sort(type2.begin(), type2.end());
    vector<int> ans;
    if (type1.size() != type2.size()) {
        if (type1.size() > type2.size()) swap(type1, type2);
        ans.emplace_back(type2.back().se);
        type2.pop_back();
    }
    int o = type1.size();
    while (o--) {
        ans.emplace_back(type1.back().se);
        ans.emplace_back(type2.back().se);
        type1.pop_back();
        type2.pop_back();
    }
    ans.emplace_back(centroid);
    return ans;
}

vector<int> sub2(vector<int> Lis, int N) {
    vector<ii> type1, type2, type3;
    for (int i = 0; i < N; i++) {
        if (i == centroid) continue;
        int dis = hoursRequired(Lis[0], i);
        if (dis + 1 == dist[i]) {
            type1.emplace_back(dist[i], i);
            nho[i] = 1;
        }
    }
    for (int i = 0; i < N; i++) {
        if (i == centroid) continue;
        int dis = hoursRequired(Lis[1], i);
        if (dis + 1 == dist[i]) {
            type2.emplace_back(dist[i], i);
            nho[i] = 1;
        }
    }
    for (int i = 0; i < N; i++)
        if (i != centroid && !nho[i]) type3.emplace_back(dist[i], i);

    sort(type1.begin(), type1.end());
    sort(type2.begin(), type2.end());
    sort(type3.begin(), type3.end());

    if (N % 2 == 0) {
        if (max({type1.size(), type2.size(), type3.size()}) == N/2) {
            vector<int> ans;
            if (type1.size() == N/2) {
                for (ii x : type3) type2.emplace_back(x);
                sort(type2.begin(), type2.end());
                ans.emplace_back(type1.back().se);
                type1.pop_back();
                int o = type2.size();
                while (o--) {
                    ans.emplace_back(type2.back().se);
                    ans.emplace_back(type1.back().se);
                    type2.pop_back();
                    type1.pop_back();
                }
            } else if (type2.size() == N/2) {
                for (ii x : type3) type1.emplace_back(x);
                sort(type1.begin(), type1.end());
                ans.emplace_back(type2.back().se);
                type2.pop_back();
                int o = type1.size();
                while (o--) {
                    ans.emplace_back(type1.back().se);
                    ans.emplace_back(type2.back().se);
                    type1.pop_back();
                    type2.pop_back();
                }
            } else {
                for (ii x : type2) type1.emplace_back(x);
                sort(type1.begin(), type1.end());
                ans.emplace_back(type3.back().se);
                type3.pop_back();
                int o = type1.size();
                while (o--) {
                    ans.emplace_back(type1.back().se);
                    ans.emplace_back(type3.back().se);
                    type1.pop_back();
                    type3.pop_back();
                }
            }
            ans.emplace_back(centroid);
            return ans;
        }
    }

    int merged = 0, last_type = 0;

    vector<int> ans;

    //casework hell..?

    while (1) {
        if (merged) {
            if (type1.empty() && type2.empty()) break;
            if (last_type == 0) {
                last_type = 1;
                ans.emplace_back(type1.back().se);
                type1.pop_back();
                continue;
            }
            if (last_type == 1) {
                last_type = 2;
                ans.emplace_back(type2.back().se);
                type2.pop_back();
                continue;
            }
            last_type = 1;
            ans.emplace_back(type1.back().se);
            type1.pop_back();
            continue;
        }
        //merge
        if (type1.size() == type2.size()+type3.size() || type2.size() == type1.size()+type3.size() || type3.size() == type1.size()+type2.size()) {
            if (type1.size() == type2.size()+type3.size()) {
                for (ii x : type3) type2.emplace_back(x);
                sort(type2.begin(), type2.end());
                if (last_type == 2 || last_type == 3) last_type = 2;
            } else if (type2.size() == type1.size()+type3.size()) {
                for (ii x : type3) type1.emplace_back(x);
                sort(type1.begin(), type1.end());
                if (last_type == 1 || last_type == 3) last_type = 1;
            } else {
                swap(type2, type3);
                for (ii x : type3) type1.emplace_back(x);
                sort(type1.begin(), type1.end());
                if (last_type == 1 || last_type == 2) last_type = 1;
            }
            merged = 1;
            continue;
        }

        //should not be empty
        assert(!type1.empty() && !type2.empty() && !type3.empty());
        if (last_type == 0) {
            int mx = max({type1.back().fi, type2.back().fi, type3.back().fi});
            if (mx == type1.back().fi) {
                last_type = 1;
                ans.emplace_back(type1.back().se);
                type1.pop_back();
                continue;
            }
            if (mx == type2.back().fi) {
                last_type = 2;
                ans.emplace_back(type2.back().se);
                type2.pop_back();
                continue;
            }
            last_type = 3;
            ans.emplace_back(type3.back().se);
            type3.pop_back();
            continue;
        }
        if (last_type == 1) {
            if (type2.back().fi >= type3.back().fi) {
                last_type = 2;
                ans.emplace_back(type2.back().se);
                type2.pop_back();
                continue;
            }
            last_type = 3;
            ans.emplace_back(type3.back().se);
            type3.pop_back();
            continue;
        }
        if (last_type == 2) {
             if (type1.back().fi >= type3.back().fi) {
                last_type = 1;
                ans.emplace_back(type1.back().se);
                type1.pop_back();
                continue;
            }
            last_type = 3;
            ans.emplace_back(type3.back().se);
            type3.pop_back();
            continue;
        }
        if (type1.back().fi >= type2.back().fi) {
            last_type = 1;
            ans.emplace_back(type1.back().se);
            type1.pop_back();
            continue;
        }
        last_type = 2;
        ans.emplace_back(type2.back().se);
        type2.pop_back();
        continue;
    }
    //should always be merged at the end..
    assert(merged);
    ans.emplace_back(centroid);
    return ans;
}

vector<int> createFunTour(int N, int Q) {
    if (N == 2) return {0, 1};

    for (int i = 0; i < N; i++) sz[i] = attractionsBehind(0, i);
    int best = INT_MAX;
    for (int i = 0; i < N; i++) if (sz[i] > N/2 && best > sz[i]) {
        centroid = i;
        best = sz[i];
    }
    for (int i = 0; i < N; i++) dist[i] = hoursRequired(centroid, i);
    vector<int> Lis;
    for (int i = 0; i < N; i++) if (dist[i] == 1) Lis.emplace_back(i);

    if (Lis.size() == 2) return sub1(Lis, N);
    return sub2(Lis, N);

}
/*
7 400000
0 1
0 5
0 6
1 2
1 4
2 3
*/

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