Submission #915677

#	Time	Username	Problem	Language	Result	Execution time	Memory
915677		gawr_gura	Airline Route Map (JOI18_airline)	C++17	100 / 100	535 ms	35948 KiB

Alice

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

#include <cassert>
#include <cstdio>

#include "Alicelib.h"

void Alice(int N, int M, int A[], int B[]) {
        if (N == 1) {
                InitG(1, 0);
                return;
        }
        vector<pair<int, int>> edge;
        for (int i = 0; i < M; i++) edge.emplace_back(A[i], B[i]);
        for (int i = 0; i < N; i++) {
                for (int j = 0; j < 10; j++) {
                        if (i >> j & 1) edge.emplace_back(i, N + j);
                }
        }
        for (int i = 0; i < N + 10; i++) edge.emplace_back(N + 10, i);
        for (int i = 0; i < 10; i++) edge.emplace_back(N + 11, N + i);
        vector<int> x(10);

        for (int i = 0; i < 5; i++) x[i] = 4 - i;
        for (int i = 5; i < 10; i++) x[i] = 5 + 9 - i;

        for (int i = 9; i >= 0; i--) {
                for (int j = 9 - i; j < i; j++) {
                        edge.emplace_back(N + x[i], N + x[j]);
                }
        }

        InitG(N + 12, edge.size());
        int cnt = 0;
        for (auto&& [a, b] : edge) MakeG(cnt++, a, b);
}

Bob

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

#include <cassert>
#include <cstdio>

#include "Boblib.h"

void Bob(int V, int U, int C[], int D[]) {
        if (V == 1) {
                InitMap(1, 0);
                return;
        }
        int N = V - 12;
        vector<int> deg(V);
        for (int i = 0; i < U; i++) deg[C[i]]++, deg[D[i]]++;
        vector<vector<bool>> c(V, vector<bool>(V));
        for (int i = 0; i < U; i++) c[C[i]][D[i]] = c[D[i]][C[i]] = true;
        int key = max_element(deg.begin(), deg.end()) - deg.begin();
        int key2 = -1;
        for (int i = 0; i < V; i++) {
                if (i == key) continue;
                if (c[key][i] == 0) {
                        key2 = i;
                }
        }
        vector<int> spec;
        for (int i = 0; i < V; i++) {
                if (c[key2][i]) spec.emplace_back(i);
        }
        for (int i = 0; i < V; i++) deg[i] -= c[key][i];
        for (int i = 0; i < V; i++) deg[i] -= c[key2][i];
        assert(spec.size() == 10);
        vector<int> sdeg(V);
        for (int i : spec) {
                for (int j : spec) sdeg[i] += c[i][j], deg[i] -= c[i][j];
        }
        sort(spec.begin(), spec.end(), [&](int i, int j) {
                return sdeg[i] < sdeg[j];
        });

        assert(sdeg[spec[4]] == sdeg[spec[5]]);
        int cnt9 = 0;
        for (int i = 0; i < N; i++) cnt9 += i >> 9 & 1;
        assert(deg[spec[4]] == cnt9 || deg[spec[5]] == cnt9);
        if (deg[spec[4]] == cnt9) swap(spec[4], spec[5]);
        vector<int> x(10);
        for (int i = 0; i < 5; i++) x[i] = 4 - i;
        for (int i = 5; i < 10; i++) x[i] = 5 + 9 - i;

        vector<int> special(V);
        special[key] = 1;
        special[key2] = 1;
        for (int i : spec) special[i] = 1;
        vector<int> num(V);
        for (int i = 0; i < 10; i++) {
                for (int j = 0; j < V; j++) {
                        if (c[spec[i]][j]) num[j] |= 1 << x[i];
                }
        }
        vector<pair<int, int>> edge;
        for (int i = 0; i < V; i++) {
                for (int j = i + 1; j < V; j++) {
                        if (special[i] || special[j]) continue;
                        if (c[i][j]) edge.emplace_back(num[i], num[j]);
                }
        }
        InitMap(V - 12, edge.size());
        for (auto&& [a, b] : edge) MakeMap(a, b);
}

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