Submission #394188

#	Time	Username	Problem	Language	Result	Execution time	Memory
394188		IloveN	Fun Tour (APIO20_fun)	C++14	100 / 100	322 ms	21340 KiB

fun

#include<bits/stdc++.h>
#include "fun.h"

using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(vr) vr.begin(),vr.end()
#define vi vector<int>
#define vll vector<ll>
const int N = 1e5 + 10;

int h[N], mark[N];

bool cmp(int obj1, int obj2) { return h[obj1] < h[obj2];}

vi createFunTour(int n, int Q) {
    //int H = hoursRequired(0, N - 1);
    //int A = attractionsBehind(0, N - 1);
    int root = 0, mn = 1e9;
    for (int i = 1; i < n; ++i)
    {
        int tmp = attractionsBehind(0, i);
        if (tmp >= (n + 1) / 2 && tmp < mn) mn = tmp, root = i;
    }
    vi sub_root;
    h[root] = 0;
    mark[root] = 1;
    for (int i = 0; i < n; ++i)
        if (i!=root)
        {
            h[i] = hoursRequired(root, i);
            if (h[i] == 1) sub_root.eb(i), mark[i] = 1;
            else mark[i] = 0;
        }
    vi subT[3];
    int n_sub = sub_root.size();
    for (int i = 0; i < n_sub; ++i) subT[i].eb(sub_root[i]);
    for (int i = 0; i < n; ++i)
        if (!mark[i])
        {
            int belong = n_sub - 1;
            for (int j = 0; j < n_sub - 1; ++j)
                if (hoursRequired(sub_root[j], i) + 1 == h[i])
                {
                    belong = j;
                    break;
                }
            subT[belong].eb(i);
        }
    int cur, mxh = -1;
    for (int i = 0; i < n_sub; ++i)
    {
        sort(all(subT[i]),cmp);
        if (h[subT[i].back()] > mxh) mxh = h[(int)subT[i].back()], cur = i;
    }
    vi ans;
    /*for (int i = 0; i < n_sub; ++i)
        for (int x : subT[i]) ans.eb(x);*/
    ans.eb(subT[cur].back());
    subT[cur].pop_back();
    for (int i = 1; i < n - 1; ++i)
    {
        if (n_sub == 3) {
        mxh  = -1;
        for (int j = 0; j < n_sub; ++j)
            if (!subT[j].empty() && h[subT[j].back()] > mxh) mxh = h[subT[j].back()];
        if (!subT[cur].empty() && h[subT[cur].back()] >= mxh)
        {
            int mx = -1, mn = 1e9, id_mx = (cur + 1) % 3, id_mn = (cur + 2) % 3;
            for (int j = 0 ; j < 3; ++j)
            if (j!=cur)
            {
                if ((int)subT[j].size() > mx) mx = subT[j].size(), id_mx = j;
                if ((int)subT[j].size() <= mn) mn = subT[j].size(), id_mn = j;
            }
            if (mx + 1 >= mn + (int)subT[cur].size())
            {
                vi vt[2];
                vt[0] = subT[id_mx];
                vt[1] = subT[cur];
                vt[1].insert(vt[1].end(),all(subT[id_mn]));
                sort(all(vt[1]),cmp);
                subT[0] = vt[0];
                subT[1] = vt[1];
                cur = 1;
                n_sub = 2;
            }
        } }
        mxh = -1;
        int nxt = cur;
        for (int j = 0; j < n_sub; ++j)
            if (cur != j && !subT[j].empty() && h[subT[j].back()] > mxh) mxh = h[subT[j].back()], nxt = j;
        cur = nxt;
        ans.eb(subT[cur].back());
        subT[cur].pop_back();
    }
    ans.eb(root);
    return ans;
}

/*int main()
{
    //freopen("ss.inp", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    return 0;
}*/

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:56:9: warning: 'cur' may be used uninitialized in this function [-Wmaybe-uninitialized]
   56 |     int cur, mxh = -1;
      |         ^~~

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