Submission #1213305

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213305		og_matveychick1	Airline Route Map (JOI18_airline)	C++20	0 / 100	353 ms	27204 KiB

Alice

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

using namespace std;

static const int N = 1500, L = 1, R = 10, M = 1;

static int n, m;
static vector<pair<int, int>> e;


void Alice(int _n, int _m, int A[], int B[]) {
    n = _n, m = _m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < R; j++) {
            if ((i >> j) & 1) e.push_back({i, n + 1 + L + j});
        }
    }
    for (int i = 0; i < m; i++) e.push_back({A[i], B[i]});
    for (int i = 0; i < n; i++) e.push_back({i, n});
    for (int i = n + 1; i < n + L + 1; i++) e.push_back({i, n});
    e.push_back({n, n + L + 1});
    for (int i = n + L + 1; i < n + L + 1 + R - 1; i++) e.push_back({i, i + 1});
    for (int i = n + 1; i < n + 1 + M; i++) {
        for (int j = n + L + 1; j < n + L + 1 + R; j++) {
            e.push_back({i, j});
        }
    }
    InitG(n + 1 + L + R, e.size());
    for (int i = 0; i < e.size(); i++) MakeG(i, e[i].first, e[i].second);
}

Bob

#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include "bits/stdc++.h"

using namespace std;

static const int N = 1500, L = 1, R = 10, M = 1;

static int n, m, p[N], cnt[N], used[N];
static vector<pair<int, int>> e;
static vector<int> g[N];
static map<vector<int>, int> ma;

void Bob(int V, int U, int C[], int D[]) {
    n = V - 1 - L - R;
    for (int i = 0; i < U; i++) {
        int u = C[i], v = D[i];
        g[u].push_back(v);
        g[v].push_back(u);
        cnt[u]++;
        cnt[v]++;
    }

    vector<int> ch(R, 3);
    ch[R - 1]--;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < R; j++) {
            if ((i >> j) & 1) ch[j]++;
        }
    }
    sort(ch.begin(), ch.end());

    int s;
    vector<int> a;
    for (int i = 0; i < V; i++) {
        if (cnt[i] != n + 2) continue;
        for (auto j: g[i]) {
            if (cnt[j] != R + 1) continue;
            vector<int> c;
            for (auto x: g[j]) {
                if (x == i) continue;
                c.push_back(cnt[x]);
            }
            sort(c.begin(), c.end());
            if (c == ch) {
                s = i;
                for (auto x: g[j]) {
                    if (x == i) continue;
                    a.push_back(x);
                }
                goto link;
            }
        }
    }
    link:

    vector<int> pt;
    int v = s;
    for (int _ = 0; _ < R; _++) {
        for (auto x: g[v]) {
            if (find(a.begin(), a.end(), x) != a.end() && !used[x]) {
                used[v] = 1;
                v = x;
                pt.push_back(v);
                break;
            }
        }
    }
    for (int i = 0; i < V; i++) {
        int id = 0;
        for (auto x: g[i]) {
            if (find(pt.begin(), pt.end(), x) != pt.end()) {
                id += 1 << (find(pt.begin(), pt.end(), x) - pt.begin());
            }
        }
        if (id < n && find(pt.begin(), pt.end(), i) == pt.end() && i != s) p[i] = id;
        else p[i] = -1;
    }
    for (int i = 0; i < V; i++) {
        if (p[i] == -1) continue;
        for (auto x: g[i]) {
            if (p[x] == -1) continue;
            if (p[x] < p[i]) continue;
            e.push_back({p[i], p[x]});
        }
    }
    InitMap(n, e.size());
    for (auto [u, w]: e) MakeMap(u, w);
}

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