oj.uz

Submission #403389

# Submission time Handle Problem Language Result Execution time Memory
403389 2021-05-13T06:35:22 Z danielcm585 Fun Tour (APIO20_fun) C++14
0 / 100
 1 ms 332 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 292 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 292 KB Output is correct
6 Runtime error 1 ms 332 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 292 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 292 KB Output is correct
6 Runtime error 1 ms 332 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Runtime error 1 ms 332 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Incorrect 1 ms 204 KB Tour is not fun
4 Halted 0 ms 0 KB -

Subtask #5
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 292 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 292 KB Output is correct
6 Runtime error 1 ms 332 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -