Submission #319467

#	Time	Username	Problem	Language	Result	Execution time	Memory
319467		VEGAnn	Fun Tour (APIO20_fun)	C++14	10 / 100	12 ms	2924 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
#define PB push_back
#define sz(x) ((int)x.size())
#define i2 array<int,2>
#define all(x) x.begin(),x.end()
using namespace std;
const int N = 100100;
vector<int> g[N], ans;
vector<i2> vc[3];
int siz[N];

void build_sz(int v, int p){
    siz[v] = 1;

    for (int u : g[v]){
        if (u == p) continue;

        build_sz(u, v);

        siz[v] += siz[u];
    }
}

int search(int v, int p, int SZ){
    for (int u : g[v]){
        if (u == p) continue;

        if (siz[u] > SZ / 2)
            return search(u, v, SZ);
    }
    return v;
}

void dfs(int v, int p, int ht, int tp){
    vc[tp].PB({ht, v});

    for (int u : g[v]){
        if (u == p) continue;

        dfs(u, v, ht + 1, tp);
    }
}

vector<int> createFunTour(int n, int Q) {
    if (n <= 500){
        for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++){
            int now = hoursRequired(i, j);

            if (now == 1){
                g[i].PB(j);
                g[j].PB(i);
            }
        }
    } else {
        for (int i = 1; i < n; i++){
            int j = (i - 1) / 2;

            g[i].PB(j);
            g[j].PB(i);
        }
    }

    ans.clear();

    build_sz(0, -1);

    int cen = search(0, -1, siz[0]);

    assert(sz(g[cen]) < 4);

    for (int it = 0; it < sz(g[cen]); it++) {
        dfs(g[cen][it], cen, 1, it);

        sort(all(vc[it]));
    }

    int mx = -1, who = -1, tp = -1;

    for (int it = 0; it < sz(g[cen]); it++)
        if (sz(vc[it]) > mx){
            mx = sz(vc[it]);
            who = vc[it].back()[1];
            tp = it;
        }

    vc[tp].pop_back();
    ans.PB(who);

    for (int itr = 2; itr < n; itr++){
        int nw_mx = -1, nw = -1, wh = -1;

        for (int it = 0; it < sz(g[cen]); it++){
            if (it == tp || sz(vc[it]) == 0) continue;

            if (sz(vc[it]) > nw_mx){
                nw_mx = sz(vc[it]);
                nw = vc[it].back()[1];
                wh = it;
            }
        }

        assert(wh >= 0);

        vc[wh].pop_back();
        ans.PB(nw);

        tp = wh;
        who = nw;
    }

    ans.PB(cen);

    return ans;
}

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