Submission #812310

#	Time	Username	Problem	Language	Result	Execution time	Memory
812310		Hanksburger	Fun Tour (APIO20_fun)	C++17	26 / 100	11 ms	2772 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
int dist[100005], bad[100005], n;
vector<int> adj[100005], ans;
queue<pair<int, int> > q;
void recur(int u)
{
    vector<int> vecL, vecR;
    if (u*2+1<n)
        vecL.push_back(u*2+1);
    for (int i=0; i<vecL.size(); i++)
    {
        if (vecL[i]*2+1<n)
            vecL.push_back(vecL[i]*2+1);
        if (vecL[i]*2+2<n)
            vecL.push_back(vecL[i]*2+2);
    }
    if (u*2+2<n)
        vecR.push_back(u*2+2);
    for (int i=0; i<vecR.size(); i++)
    {
        if (vecR[i]*2+1<n)
            vecR.push_back(vecR[i]*2+1);
        if (vecR[i]*2+2<n)
            vecR.push_back(vecR[i]*2+2);
    }
    reverse(vecL.begin(), vecL.end());
    reverse(vecR.begin(), vecR.end());
    for (int i=0; i<vecR.size(); i++)
    {
        ans.push_back(vecL[i]);
        ans.push_back(vecR[i]);
    }
    if (vecL.size()==vecR.size())
        ans.push_back(u);
    else if (vecL.size()==vecR.size()+1)
    {
        ans.push_back(vecL[vecR.size()]);
        ans.push_back(u);
    }
    else
    {
        ans.push_back(vecL[vecR.size()]);
        ans.push_back(u);
        n=vecL[vecR.size()];
        recur(u*2+1);
    }
}
vector<int> createFunTour(int nn, int qq)
{
    n=nn;
    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);
                }
            }
        }
        int cur=0;
        for (int i=0; i<n; i++)
        {
            for (int j=0; j<n; j++)
            dist[j]=1e9;
            dist[cur]=0;
            q.push({cur, -1});
            while (!q.empty())
            {
                int u=q.front().first, p=q.front().second;
                q.pop();
                for (int v:adj[u])
                {
                    if (v==p || bad[v])
                    continue;
                    dist[v]=dist[u]+1;
                    q.push({v, u});
                }
            }
            int ind, mx=-1;
            for (int j=0; j<n; j++)
            {
                if (!bad[j] && mx<dist[j])
                {
                    mx=dist[j];
                    ind=j;
                }
            }
            ans.push_back(ind);
            bad[ind]=1;
            cur=ind;
        }
        return ans;
    }
    recur(0);
    return ans;
}

Compilation message (stderr)

fun.cpp: In function 'void recur(int)':
fun.cpp:12:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for (int i=0; i<vecL.size(); i++)
      |                   ~^~~~~~~~~~~~
fun.cpp:21:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for (int i=0; i<vecR.size(); i++)
      |                   ~^~~~~~~~~~~~
fun.cpp:30:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int i=0; i<vecR.size(); i++)
      |                   ~^~~~~~~~~~~~

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