Submission #725091

#	Time	Username	Problem	Language	Result	Execution time	Memory
725091		danikoynov	Fun Tour (APIO20_fun)	C++14	26 / 100	37 ms	15676 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;
        vector < int > ans;
        ans.push_back(cur);
        for (int step = 1; step < N; step ++)
        {
            int v = cur;
            while(v != -1)
            {
                sub[v].erase({cur, depth[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];
            }

            if (up == -1)
            {
                v = par[cur];
                while(v != -1)
                {
                    ans.push_back(v);
                    v = par[v];
                }
                break;
            }

            for (int child : g[par[up]])
            {
                if (child != up)
                {
                    cur = sub[child].rbegin() -> second;
                }
            }
            ans.push_back(cur);
        }
    }
    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;
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:53:17: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   53 |                 if (sub[par[v]].size() != sub[v].size())
      |                 ^~
fun.cpp:55:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   55 |                     v = par[v];
      |                     ^

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