Submission #403389

#	Time	Username	Problem	Language	Result	Execution time	Memory
403389		danielcm585	Fun Tour (APIO20_fun)	C++14	0 / 100	1 ms	332 KiB

fun

#include "fun.h"

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second

typedef pair<int,int> ii;

const int INF = 1e9;

vector<int> createFunTour(int N, int Q) {
    vector<int> dep(N);
    vector<ii> dis;
    for (int i = 0; i < N; i++) {
        dep[i] = hoursRequired(0,i);
        dis.push_back(ii(dep[i],i));
    }
    int cent = 0;
    vector<int> brch;
    sort(dis.begin(),dis.end());
    for (auto i : dis) {
        if (dep[i.se] == dep[cent]+1) {
            brch.push_back(i.se);
            if (attractionsBehind(0,i.se)*2 >= N) {
                cent = i.se;
                brch.clear();
            }
        }
    }
    // cout << ">> " << cent << '\n';
    vector<ii> lst[3];
    if (!cent) {
        for (int i = N-1; i >= 1; i--) {
            for (int j : {0,1,2}) {
                if (hoursRequired(brch[j],dis[i].se) == dep[dis[i].se]-1) {
                    lst[j].push_back(dis[i]);
                    break;
                }
            }
        }
    }
    else {
        for (int i = N-1; i >= 0; i--) {
            if (dis[i].se == cent) continue;
            bool done = 0;
            for (int j : {0,1}) {
                if (hoursRequired(brch[j],dis[i].se) == dep[dis[i].se]-dep[brch[j]]) {
                    lst[j].push_back(dis[i]);
                    done = 1;
                    break;
                }
            }
            if (done) continue;
            lst[2].push_back(ii(hoursRequired(cent,dis[i].se),dis[i].se));
        }
        sort(lst[2].rbegin(),lst[2].rend());
    }
    int ls = -1;
    vector<int> res;
    res.push_back(cent);
    for (int i = 0; i < N-1; i++) {
        int cur = -1;
        for (int j : {0,1,2}) {
            if (j == ls || lst[j].empty()) continue;
            if (cur == -1 || lst[j].back().fi < lst[cur].back().fi || lst[j].back().fi == lst[cur].back().fi && lst[j].size() > lst[cur].size()) {
                cur = j;
            }
        }
        assert(cur != -1);
        res.push_back(lst[cur].back().se);
        lst[cur].pop_back();
        ls = cur;
        // cout << res.back() << ' ';
    }
    // cout << '\n';
    reverse(res.begin(),res.end());
    return res;
}

/*
7 400000
0 1 
0 5
0 6
1 2
1 4
2 3
*/

Compilation message (stderr)

fun.cpp: In function 'std::vector<int> createFunTour(int, int)':
fun.cpp:67:110: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   67 |             if (cur == -1 || lst[j].back().fi < lst[cur].back().fi || lst[j].back().fi == lst[cur].back().fi && lst[j].size() > lst[cur].size()) {
      |                                                                       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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