Submission #1161866

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161866		The_Samurai	즐거운 행로 (APIO20_fun)	C++20	10 / 100	1342 ms	77956 KiB

fun

#include "fun.h"
#include "bits/stdc++.h"
using namespace std;
const int N = 1 << 27;

int code(int bt, int x, int d) {
    return bt | (x << 17) | (d << 22);
}

tuple<int, int, int> decode(int c) {
    int bt = c % (1 << 17); c >>= 17;
    int x = c % (1 << 5); c >>= 5;
    return tuple{bt, x, c};
}

std::vector<int> createFunTour(int n, int q) {
    vector dist(n, vector(n, 0));
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
        dist[i][j] = hoursRequired(i, j);
    }
    
    queue<int> qq;
    map<int, int> par;
    for (int i = 0; i < n; i++) {
        int c = code(1 << i, i, 1);
        qq.push(c); par[c] = 0;
    }

    int way = -1;
    while (!qq.empty()) {
        int c = qq.front(); qq.pop();
        auto [bt, x, d] = decode(c);
        if (bt == (1 << n) - 1) {
            way = c;
            break;
        }
        for (int y = 0; y < n; y++) {
            if (bt & (1 << y)) continue;
            if (dist[x][y] >= d) {
                int nc = code(bt ^ (1 << y), y, dist[x][y]);
                if (par.count(nc)) continue;
                qq.push(nc);
                par[nc] = c;
            }
        }
    }
    assert(way != -1);
    vector<int> ans;
    while (way != 0) {
        auto [bt, x, d] = decode(way);
        ans.emplace_back(x);
        way = par[way];
    }
    return ans;
}

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