Submission #1226006

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226006		KALARRY	Fun Tour (APIO20_fun)	C++20	10 / 100	219 ms	36776 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)];

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);
    for(int i = 0 ; i < N ; i++)
    {
        int mask = ((1<<N) - 1 ) ^ (1<<i);
        dp[i][mask] = INF;
    }
    for(int mask = (1<<N) - 1 ; mask >= 0 ; mask--)
        for(int i = 0 ; i < N ; i++)
        {
            if(mask == (((1<<N) - 1 ) ^ (1<<i)))
                continue;
            dp[i][mask] = -1;
            
            if(mask & (1<<i))
                continue;
            int new_mask = mask ^ (1<<i);
            for(int j = 0 ; j < N ; j++)
            if(!(new_mask & (1<<j)))
            {
                if(dist[i][j] <= dp[j][new_mask] && dist[i][j] > dp[i][mask])
                {
                    dp[i][mask] = dist[i][j];
                    par[i][mask] = j;
                }
            }
        }
    for(int i = 0 ; i < N ; i++)
        if(dp[i][0] != -1)
        {
            find_path(i,0);
            break;
        }
    vector<int> ret;
    while(!ans.empty())
    {
        ret.push_back(ans.top());
        ans.pop();
    }
    return ret;
}

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