Submission #725095

#	Time	Username	Problem	Language	Result	Execution time	Memory
725095		danikoynov	Fun Tour (APIO20_fun)	C++14	47 / 100	489 ms	103688 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 nxt = -1, dis = -10;
            if (!sub[cur].empty())
            {
                nxt = sub[cur].rbegin() -> second;
                dis = sub[cur].rbegin() -> first - depth[cur];
            }

            v = cur;
            while(v != 0)
            {
                for (int child : g[par[v]])
                {
                    if (child == v)
                        continue;
                    if (sub[child].size() == 0)
                        continue;
                        ///cout << "here " << child << endl;
                    int len = sub[child].rbegin() -> first + depth[cur] - 2 * depth[par[v]];
                    ///cout << len << " " << dis << endl;
                    if (len > dis)
                    {
                        dis = len;
                        nxt = sub[child].rbegin() -> second;
                        ///cout << nxt << endl;
                    }
                }
                if (sub[par[v]].size() > sub[v].size())
                {
                    if (depth[cur] - depth[par[v]] > dis)
                    {
                        dis = depth[cur] - depth[par[v]];
                        nxt = par[v];
                    }
                }
                v = par[v];
            }
            cur = nxt;
            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: 21 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 34