Submission #979127

#	Time	Username	Problem	Language	Result	Execution time	Memory
979127		Tuanlinh123	Fun Tour (APIO20_fun)	C++17	0 / 100	1 ms	856 KiB

fun

#include "fun.h"
#include<bits/stdc++.h>
#define ll int
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;

const ll maxn=100005;
ll dist(ll a, ll b) {return hoursRequired(a, b);}
ll subcnt(ll a, ll b) {return attractionsBehind(a, b);}

vector<int> createFunTour(int n, int Q) 
{
    ll g=0;
    // findcentroid 
    {
        ll cr=n;
        for (ll j=1; j<n; j++)
        {
            ll x=subcnt(0, j);
            if (x*2>=n && x<=cr)
                g=j, cr=x;
        }
    }
    vector <pll> dis;
    vector <vector <pll>> branch;
    for (ll i=0; i<n; i++)
        if (i!=g)
        {
            dis.pb({dist(g, i), i});
            if (dis.back().fi==1) branch.pb(vector <pll> {{1, i}});
        } 
    for (auto [d, i]:dis)
        for (ll j=0; j<sz(branch); j++)
        {
            if (j+1==sz(branch)) branch[j].pb({d, i});
            else if (dist(i, branch[j][0].se)+1==d) {branch[j].pb({d, i}); break;}
        }
    for (ll j=0; j<sz(branch); j++) sort(branch[j].begin(), branch[j].end(), greater<pll>());
    vector <ll> tour;
    // case 1
    if (sz(branch)==2)
    {
        if (sz(branch[0])<sz(branch[1])) swap(branch[0], branch[1]);
        for (ll ptr[2]={}, t=0; sz(tour)+1<n; ptr[t]++, t^=1)
            tour.pb(branch[t][ptr[t]].se);
        return tour.pb(g), tour;
    }
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:30:18: warning: control reaches end of non-void function [-Wreturn-type]
   30 |     vector <pll> dis;
      |                  ^~~

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