제출 #1136845

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1136845		adaawf	항공 노선도 (JOI18_airline)	C++20	0 / 100	177 ms	25940 KiB

Alice

#include <bits/stdc++.h>
#include "Alicelib.h"
using namespace std;
vector<int> g[2005];
void Alice(int n, int m, int a[], int b[]) {
    for (int i = 0; i < m; i++) {
        g[a[i]].push_back(b[i]);
    }
    for (int i = 0; i < 10; i++) {
        for (int j = 1; j <= n; j++) {
            if (j & (1 << i)) {
                g[n + i].push_back(j - 1);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        g[n + 10].push_back(i);
        g[n + 11].push_back(i);
    }
    for (int i = 0; i < 4; i++) {
        for (int j = 1; j <= 8; j++) {
            if (j & (1 << i)) {
                g[n + 8 + i].push_back(n + j - 1);
            }
        }
    }
    g[n + 11].push_back(n + 8);
    g[n + 10].push_back(n + 9);
    for (int i = 0; i < 7; i++) {
        g[n + 7].push_back(n + i);
    }
    int c = 0;
    for (int i = 0; i < n + 12; i++) {
        c = c + g[i].size();
    }
    InitG(n + 12, c);
    c = 0;
    for (int i = 0; i < n + 12; i++) {
        for (int w : g[i]) {
            MakeG(c, i, w);
            c++;
        }
    }
}

Bob

#include <bits/stdc++.h>
#include "Boblib.h"
using namespace std;
vector<int> g[2005];
int dd[2005][2005], da[2005], db[2005], res[2005], dc[2005];
void Bob(int n, int m, int a[], int b[]) {
    for (int i = 0; i < n; i++) g[i].clear();
    for (int i = 0; i < m; i++) {
        g[a[i]].push_back(b[i]);
        g[b[i]].push_back(a[i]);
        dd[a[i]][b[i]] = 1;
        dd[b[i]][a[i]] = 1;
    }
    n -= 12;
    int x = 0, y = 0;
    for (int i = 0; i < n + 12; i++) {
        if (g[i].size() == n + 2) {
            x = i;
        }
        if (g[i].size() == n + 5) {
            y = i;
        }
    }
    for (int w : g[x]) {
        if (dd[y][w] == 1) {
            da[w] = 1;
        }
    }
    int b7, b8, b9, mi = 1e9, ma = -1;
    for (int w : g[x]) {
        if (da[w] == 1) continue;
        int c = 0;
        for (int ww : g[w]) {
            if (da[ww] == 0) c++;
        }
        if (mi > c) {
            mi = c;
            b8 = w;
        }
        if (ma < c) {
            ma = c;
            b7 = w;
        }
    }
    db[b7] = 1;
    for (int w : g[b7]) {
        if (da[w] == 1 || w == x) continue;
        db[w] = 1;
    }
    for (int w : g[y]) {
        if (da[w] == 1) continue;
        if (db[w] == 0) {
            b9 = w;
            break;
        }
    }
    db[b8] = db[b9] = 1;
    for (int w : g[x]) if (db[w] == 1) dc[w] += (1 << 3);
    for (int w : g[y]) if (db[w] == 1) dc[w] += (1 << 2);
    for (int w : g[b8]) if (db[w] == 1) dc[w] += (1 << 0);
    for (int w : g[b9]) if (db[w] == 1) dc[w] += (1 << 1);
    for (int i = 0; i < n + 12; i++) {
        if (db[i] == 0) continue;
        dc[i]--;
        for (int w : g[i]) {
            if (da[w] == 0) continue;
            res[w] += (1 << dc[i]);
        }
    }
    vector<pair<int, int>> v;
    for (int i = 0; i < n + 12; i++) {
        if (da[i] == 0) continue;
        for (int w : g[i]) {
            if (da[w] == 0 || i < w) continue;
            v.push_back({res[i] - 1, res[w] - 1});
        }
    }
    InitMap(n, v.size());
    for (auto w : v) {
        MakeMap(w.first, w.second);
    }
}

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