Submission #812857

#	Time	Username	Problem	Language	Result	Execution time	Memory
812857		Hanksburger	Fun Tour (APIO20_fun)	C++17	0 / 100	837 ms	161544 KiB

fun

#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
int res1[100005], res2[100005], par[100005], depth[100005], n;
queue<pair<int, pair<int, int> > > q;
vector<pair<int, int> > des[100005];
vector<int> child[100005], vec, ans;
set<pair<int, int> > s[100005];
void dfs(int u)
{
    s[u].insert({-depth[u], u});
    for (int v:child[u])
    {
        depth[v]=depth[u]+1;
        dfs(v);
        s[u].insert(s[v].begin(), s[v].end());
    }
}
vector<int> createFunTour(int nn, int qq)
{
    n=nn;
    int len=hoursRequired(0, n-1);
    vec.push_back(0);
    for (int i=1; i<=n-2; i++)
    {
        res1[i]=hoursRequired(0, i);
        res2[i]=hoursRequired(i, n-1);
        if (res1[i]+res2[i]==len)
            vec.push_back(i);
        else
            des[res1[i]-(res1[i]+res2[i]-len)/2].push_back({(res1[i]+res2[i]-len)/2, i});
    }
    vec.push_back(n-1);
    for (int i=0; i<=vec.size()-2; i++)
    {
        child[vec[i]].push_back(vec[i+1]);
        par[vec[i+1]]=vec[i];
    }
    for (int i=0; i<vec.size(); i++)
    {
        sort(des[i].begin(), des[i].end());
        int ind=0;
        q.push({vec[i], {0, -1}});
        q.push({vec[i], {0, n}});
        while (!q.empty())
        {
            int u=q.front().first, v=q.front().second.first, w=q.front().second.second;
            q.pop();
            while (ind<des[i].size() && des[i][ind].first==v+1 && (des[i][ind].second-u)*(w-des[i][ind].second)>0)
            {
                child[u].push_back(des[i][ind].second);
                par[des[i][ind].second]=u;
                if (u<w)
                {
                    q.push({des[i][ind].second, {v+1, u}});
                    q.push({des[i][ind].second, {v+1, w}});
                }
                else
                {
                    q.push({des[i][ind].second, {v+1, w}});
                    q.push({des[i][ind].second, {v+1, u}});
                }
                ind++;
            }
        }
    }
    dfs(0);
    int cur, d=0;
    for (int i=0; i<n; i++)
    {
        if (d<depth[i])
        {
            d=depth[i];
            cur=i;
        }
    }
    ans.push_back(cur);
    {
        int u=cur;
        while (u)
        {
            s[u].erase({-depth[cur], cur});
            u=par[u];
        }
        s[u].erase({-depth[cur], cur});
    }
    for (int i=1; i<n; i++)
    {
        int u=cur, cnt=1, mx=0, ind;
        while (u)
        {
            cnt++;
            int p=par[u];
            for (int v:child[p])
            {
                if (v!=u && s[v].size() && mx<cnt-depth[v]-(*s[v].begin()).first)
                {
                    mx=cnt-depth[v]-(*s[v].begin()).first;
                    ind=(*s[v].begin()).second;
                }
            }
            u=p;
        }
        if (mx)
            cur=ind;
        else
            cur=par[cur];
        ans.push_back(cur);
        {
            int u=cur;
            while (u)
            {
                s[u].erase({-depth[cur], cur});
                u=par[u];
            }
            s[u].erase({-depth[cur], cur});
        }
    }
    return ans;
}

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:34:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for (int i=0; i<=vec.size()-2; i++)
      |                   ~^~~~~~~~~~~~~~
fun.cpp:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for (int i=0; i<vec.size(); i++)
      |                   ~^~~~~~~~~~~
fun.cpp:49:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |             while (ind<des[i].size() && des[i][ind].first==v+1 && (des[i][ind].second-u)*(w-des[i][ind].second)>0)
      |                    ~~~^~~~~~~~~~~~~~

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