Submission #1225037

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225037		Double_Slash	Airline Route Map (JOI18_airline)	C++20	100 / 100	786 ms	64872 KiB

Alice

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

using namespace std;
using pint = pair<int, int>;

void Alice(int N, int M, int A[], int B[]) {
    vector<pint> edges{{N + 10, N + 11}};
    while (M--) edges.emplace_back(A[M], B[M]);
    for (int i = 0, idx = 0; i < N; ++i) {
        while (__builtin_popcount(++idx) < 2);
        for (int j = 10; j--;) {
            if ((idx >> j) & 1) edges.emplace_back(i, N + j);
        }
    }
    for (int i = 10; i--;) edges.emplace_back(N + i, N + 10);
    for (int i = 10; --i;) edges.emplace_back(N + i - 1, N + i);
    InitG(N + 12, edges.size());
    for (int i = edges.size(); i--;) MakeG(i, edges[i].first, edges[i].second);
}

Bob

#include "Boblib.h"
#include <bits/stdc++.h>
 
using namespace std;
#define all(x) x.begin(), x.end()
using pint = pair<int, int>;

set<int> adj[1012];

void Bob(int V, int U, int C[], int D[]) {
    bool ban[V]{};
    while (U--) {
        adj[C[U]].emplace(D[U]);
        adj[D[U]].emplace(C[U]);
    }
    set<int> raw;
    for (int i = V; i--;) {
        if (adj[i].size() > 1) continue;
        raw = adj[*adj[i].begin()];
        raw.erase(i);
        ban[*adj[i].begin()] = ban[i] = true;
        for (int j: raw) ban[j] = true;
    }
    vector<int> order;
    for (int i: raw) {
        int cnt = 0;
        for (int j: raw) cnt += adj[i].count(j);
        if (cnt > 1) continue;
        order = {i};
        raw.erase(i);
        while (order.size() < 10) {
            for (int j: raw) {
                if (not adj[order.back()].count(j)) continue;
                order.emplace_back(j);
                raw.erase(j);
                break;
            }
        }
        break;
    }
    int idx[1 << 10]{};
    for (int i = 0, j = 0; ++i <= V - 12;) {
        while (__builtin_popcount(++j) < 2);
        j[idx] = i;
    }
    if (false) rev: reverse(all(order));
    int real[V];
    for (int i = V; i--;) {
        if (ban[i]) continue;
        int x = 0;
        for (int j = 10; j--;) x |= adj[i].count(order[j]) << j;
        if (not idx[x] or (real[i] = idx[x] - 1) >= V - 12) goto rev;
    }
    vector<pint> edges;
    for (int i = V; i--;) {
        if (ban[i]) continue;
        for (int j: adj[i]) {
            if (not ban[j] and j < i) edges.emplace_back(real[i], real[j]);
        }
    }
    InitMap(V - 12, edges.size());
    for (auto [a, b]: edges) MakeMap(a, b);
}

• Subtask 1: 22 / 22
• Subtask 2: 15 / 15
• Subtask 3: 63 / 63