Submission #1226049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226049		KALARRY	Fun Tour (APIO20_fun)	C++20	26 / 100	15 ms	3796 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);

vector<int> adj[100005];
int n,dist[505][505],dp[20][(1<<19)],par[20][(1<<19)];
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;

void find_path(int i,int mask)
{
    ans.push(i);
    int j = par[i][mask];
    int new_mask = mask ^ (1<<i);
    if(new_mask == (1<<n) - 1)
        return;
    find_path(j,new_mask);
}

std::vector<int> createFunTour(int N, int Q) 
{
    n = N;
    int H = hoursRequired(0, N - 1);
    int A = attractionsBehind(0, N - 1);
    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);
    vector<int> ret;
    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] >= 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