Submission #1226082

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226082		KALARRY	Fun Tour (APIO20_fun)	C++20	0 / 100	5 ms	12100 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,par[100005];
vector<int> adj[100005];
set<pair<int,int>> dist_left[100005];
set<pair<int,int>> dist_right[100005];
bool used[5005];

void dfs(int v,int p)
{
    par[v] = p;
    dist_left[v].insert({0,v});
    dist_right[v].insert({0,v});
    for(auto u : adj[v])
        if(u != p)
        {
            dfs(u,v);
            if(u == 2*v + 1)
            {
                for(auto x : dist_left[u])
                    dist_left[v].insert({x.first+1,x.second});
                for(auto x : dist_right[u])
                    dist_left[v].insert({x.first+1,x.second});   
            }
            else
            {
                for(auto x : dist_left[u])
                    dist_right[v].insert({x.first+1,x.second});
                for(auto x : dist_right[u])
                    dist_right[v].insert({x.first+1,x.second});   
            }
        }
    // printf("\n\n%d containts: \n",v);
    // printf("Left: ");
    // for(auto x : dist_left[v])
    //     printf("(%d,%d)  ",x.first,x.second);
    // printf("\n\n");

    // printf("right: ");
    // for(auto x : dist_right[v])
    //     printf("(%d,%d)  ",x.first,x.second);
    // printf("\n\n");
}

pair<int,int> find_max_dist(int i)
{
    pair<int,int> max_dist = {0,0};
    if(!dist_left[i].empty())
        max_dist = *dist_left[i].rbegin();
    if(!dist_right[i].empty())
        max_dist = max(max_dist,*dist_right[i].rbegin());

    int extra = 0;
    while(i != par[i])
    {
        extra++;
        bool come_from_left = true;
        int p = par[i];
        if(i==2*p + 2)
            come_from_left = false;
        pair<int,int> cur_dist = {0,0};
        if(come_from_left)
        {
            if(!dist_right[p].empty())
                cur_dist = *dist_right[p].rbegin();
        }
        else
        {
            if(!dist_left[p].empty())
                cur_dist = *dist_left[p].rbegin();
        }
        // printf("For %d found %d %d\n",p,cur_dist.first,cur_dist.second);
        if(cur_dist.second != 0)
            cur_dist.first += extra;
        max_dist = max(max_dist,cur_dist);
        i = p;
    }
    return max_dist;
}

void remove_node(int v)
{
    int cur_dist = 0;
    dist_left[v].erase({0,v});
    dist_right[v].erase({0,v});
    int i = v;
    while(i != par[i])
    {
        cur_dist++;
        int p = par[i];
        bool come_from_left = true;
        if(i==2*p+2)
            come_from_left = false;
        if(come_from_left)
            dist_left[p].erase({cur_dist,v});
        else
            dist_right[p].erase({cur_dist,v});
        i = par[i];
    }
}

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);
                }
            }
    }
    else
    {
        for(int i = 1 ; i < N ; i++)
        {
            par[i] = (i-1)/2;
            adj[i].push_back(par[i]);
            adj[par[i]].push_back(i);
        }
    }
    dfs(0,0);
    int i = N-1;
    pair<int,int> new_dist = find_max_dist(i);
    // printf("new_dist = %d %d\n",new_dist.first,new_dist.second);
    int j = new_dist.second;
    ret.push_back(i);
    ret.push_back(j);
    int prev = j;
    remove_node(i);
    remove_node(j);
    int counter = 2;
    while(counter < N)
    {
        new_dist = find_max_dist(prev);
        int y = new_dist.second;
        ret.push_back(y);
        prev = y;
        remove_node(y);
        counter++;
    }
    return ret;
}

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