Submission #1226031

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226031		KALARRY	Fun Tour (APIO20_fun)	C++20	26 / 100	12 ms	8520 KiB

fun

//chockolateman

#include<bits/stdc++.h>
#include "fun.h"

using namespace std;

const int INF = 1e9;

int hoursRequired(int X, int Y);
int attractionsBehind(int X, int Y);

int n,dist[505][505];
vector<int> adj[100005];
set<int> distances[100005];
bool used[5005];

void dfs(int v,int p,int root)
{
    for(auto u : adj[v])
        if(u != p)
        {
            dist[root][u] = dist[root][v] + 1;
            dfs(u,v,root);
        }
}

stack<int> ans;

std::vector<int> createFunTour(int N, int Q) 
{
    n = N;
    int H = hoursRequired(0, N - 1);
    int A = attractionsBehind(0, N - 1);
    vector<int> ret;
    if(n <= 500)
    {
        for(int i = 0 ; i < N ; i++)
            for(int j = i+1 ; j < N ; j++)
            {
                if(hoursRequired(i, j) == 1)
                {
                    adj[i].push_back(j);
                    adj[j].push_back(i);
                }
            }
            for(int i = 0 ; i < N ; i++)
                dfs(i,i,i);
            int cur_dist = 0;
            int i,j;
            for(int x = 0 ; x < N ; x++)
                for(int y = x+1 ; y < N ; y++)
                    if(dist[x][y] > cur_dist)
                    {
                        i = x;
                        j = y;
                        cur_dist = dist[x][y];
                    }
            ret.push_back(i);
            ret.push_back(j);
            int prev = j;
            used[i] = true;
            used[j] = true;
            int counter = 2;
            while(counter < N)
            {
                int prev_dist = cur_dist;
                int y = 1;
                cur_dist = 0;
                for(int x = 0 ; x < N ; x++)
                    if(!used[x] && dist[prev][x] <= prev_dist && dist[prev][x] >= cur_dist)
                    {
                        y = x;
                        cur_dist = dist[prev][x];
                    }
                ret.push_back(y);
                prev = y;
                used[y] = true;
                counter++;
            }
    }

    return ret;
}

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