Submission #725093

#	Time	Username	Problem	Language	Result	Execution time	Memory
725093		danikoynov	Fun Tour (APIO20_fun)	C++14	26 / 100	29 ms	15468 KiB

fun

#include "fun.h"

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

const int maxn = 2e5 + 10;
int dis[510][510], used[maxn], par[maxn], depth[maxn];
vector < int > g[maxn];

set < pair < int, int > > sub[maxn];

void dfs(int v)
{
    sub[v].insert({depth[v], v});
    for (int u : g[v])
    {
        depth[u] = depth[v] + 1;
        par[u] = v;
        dfs(u);
        for (pair < int, int > nb : sub[u])
            sub[v].insert(nb);
    }
}


vector<int> createFunTour(int N, int Q)
{
    if (N > 500)
    {
        for (int i = 1; i < N; i ++)
        {
            g[(i - 1) / 2].push_back(i);
        }
        par[0] = -1;
        dfs(0);

        int cur = N - 1;
        vector < int > ans;
        ans.push_back(cur);
        for (int step = 1; step < N; step ++)
        {
            ///cout << cur << endl;
            int v = cur;
            while(v != -1)
            {

                sub[v].erase({depth[cur], cur});
                v = par[v];
            }

            int up = -1;
            v = cur;
            while(v != 0)
            {
                if (sub[par[v]].size() != sub[v].size())
                    up = v;
                v = par[v];
            }
            ///cout << "here " << up << " " << cur << " " << sub[up].size() << endl;
            if (up == -1)
            {
                cur = sub[cur].rbegin() -> second;
            }
            else
            if (par[up] != -1 && sub[par[up]].size() == sub[up].size() + 1)
            {
                ///cout << "alone" << endl;
                cur = par[up];
            }
            else
            {
                for (int child : g[par[up]])
                {
                    if (child != up && sub[child].size() > 0)
                    {
                        ///cout << "child " << endl;
                        cur = sub[child].rbegin() -> second;
                    }
                }
            }

            ans.push_back(cur);
        }
        //for (int v : ans)
         //   cout << v << " ";
        //cout << endl;
        return ans;
    }
    for (int i = 0; i < N; i ++)
        for (int j = 0; j < N; j ++)
        {
            dis[i][j] = hoursRequired(i, j);
        }

    int cur = 0;
    for (int i = 1; i < N; i ++)
        if (dis[0][i] > dis[0][cur])
            cur = i;

    vector < int > ans;
    ans.push_back(cur);
    used[cur] = 1;
    for (int i = 1; i < N; i ++)
    {
        int v = 1;
        while(used[v] == 1)
            v ++;

        for (int j = 0; j < N; j ++)
        {
            if (used[j])
                continue;
            if (dis[cur][j] > dis[cur][v])
                v = j;
        }

        ans.push_back(v);
        used[v] = 1;
        cur = v;
    }

    return ans;
}

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