Submission #319456

#	Time	Username	Problem	Language	Result	Execution time	Memory
319456		VEGAnn	Fun Tour (APIO20_fun)	C++14	0 / 100	6 ms	5228 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
#define PB push_back
#define sz(x) ((int)x.size())
#define i2 array<int,2>
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) {
    assert(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);
        }
    }

    ans.clear();

    build_sz(0, -1);

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

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

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

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

    for (int it = 0; it < sz(g[cen]); it++)
        if (vc[it].back()[0] > mx){
            mx = vc[it].back()[0];
            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 (vc[it].back()[0] > nw_mx){
                nw_mx = vc[it].back()[0];
                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: 0 / 10
• Subtask 2: 0 / 16
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 34