제출 #1147442

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1147442		onbert	Airline Route Map (JOI18_airline)	C++20	100 / 100	175 ms	23216 KiB

Alice

#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;

void Alice( int n, int m, int A[], int B[] ){
    vector<pair<int,int>> edge;
    edge.clear();
	for (int i=0;i<=n+9;i++) edge.push_back({i, n+10});
    for (int i=n;i<=n+9;i++) edge.push_back({i, n+11});
    for (int i=0;i<m;i++) edge.push_back({A[i], B[i]});
    for (int i=n;i<n+9;i++) edge.push_back({i, i+1});
    for (int i=0;i<n;i++) {
        for (int j=0;j<10;j++) if (i & (1<<j)) edge.push_back({i, j+n});
    }
    int sz = edge.size();
    // cout << n + 12 << " " << sz << endl;
    // for (auto [u, v]:edge) cout << u << " " << v << endl;
    InitG(n + 12, sz);
    for (int i=0;i<sz;i++) MakeG(i, edge[i].first, edge[i].second);
}

Bob

#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1020;
int deg[maxn];
bool is[maxn][maxn];
vector<int> adj[maxn];
bool rl[maxn];
int id[maxn];
int decode[maxn], bit[10];


void Bob( int V, int M, int C[], int D[] ){
    vector<pair<int,int>> edge;
    for (int i=0;i<V;i++) deg[i] = 0, rl[i] = true, adj[i].clear();
    for (int i=0;i<V;i++) for (int j=0;j<V;j++) is[i][j] = false;
    // cout << V << " " << M << endl;
    // for (int i=0;i<M;i++) cout << C[i] << " " << D[i] << endl;
    int n = V - 12;
    for (int i=0;i<V;i++) deg[i] = 0;
    for (int i=0;i<M;i++) {
        adj[C[i]].push_back(D[i]);
        adj[D[i]].push_back(C[i]);
        deg[C[i]]++, deg[D[i]]++;
        is[C[i]][D[i]] = is[D[i]][C[i]] = true;
    }
    int hub;
    for (int i=0;i<V;i++) if (deg[i] == V-2) hub = i;
    int key;
    for (int i=0;i<V;i++) if (i != hub && !is[hub][i]) key = i;
    // cout << hub << " " << key << endl;
    rl[hub] = rl[key] = false;
    vector<int> funny;
    for (int i=0;i<V;i++) if (is[key][i]) {
        funny.push_back(i);
        rl[i] = false;
    }
    for (int i=0;i<V;i++) deg[i] = 0;
    for (int i=0;i<10;i++) for (int j=0;j<10;j++) {
        deg[funny[i]] += is[funny[i]][funny[j]];
    }
    // for (int i:funny) cout << i << " "; cout << endl;

    for (int i:funny) if (deg[i] == 1) bit[0] = i;
    for (int i=1;i<=9;i++) {
        for (int j:funny) if (is[j][bit[i-1]] && (i-2 < 0 || j != bit[i-2])) bit[i] = j;
    }

    // for (int i=0;i<10;i++) cout << bit[i] << " "; cout << endl;

    // for (int i=0;i<V;i++) cout << rl[i] << " "; cout << endl;

    bool redo = false;
    for (int i=0;i<n;i++) decode[i] = -1;
    for (int i=0;i<V;i++) id[i] = -1;
    for (int i=0;i<V;i++) if (rl[i]) {
        id[i] = 0;
        for (int j=0;j<10;j++) if (is[i][bit[j]]) id[i] += (1<<j);
        if (id[i] >= n) {
            redo = true;
            // cout << i << " " << id[i] << endl;
            break;
        }
        decode[id[i]] = i;
    }
    // cout << redo << endl;
    for (int i=0;i<n;i++) if (decode[i] == -1) redo = true;
    // for (int i=0;i<V;i++) cout << id[i] << " "; cout << endl;
    // for (int i=0;i<10;i++) cout << bit[i] << " "; cout << endl;
    // for (int i=0;i<10;i++) cout << deg[bit[i]] << " "; cout << endl;
    if (redo) {
        reverse(bit, bit+10);
        for (int i=0;i<V;i++) if (rl[i]) {
            id[i] = 0;
            for (int j=0;j<10;j++) if (is[i][bit[j]]) id[i] += (1<<j);
            // cout << id[i] << " ";
        }
        // cout << endl;
    }
    // for (int i=0;i<10;i++) cout << bit[i] << " "; cout << endl;

    // for (int i:funny) cout << i << " "; cout << endl;
    // for (int i=0;i<10;i++) cout << bit[i] << " "; cout << endl;
    for (int i=0;i<M;i++) {
        int u = C[i], v = D[i];
        if (rl[u] && rl[v]) {
            edge.push_back({id[u], id[v]});
            // cout << u << " " << v << " " << id[u] << " " << id[v] << endl;
        }
    }
    // for (int i=0;i<V;i++) cout << id[i] << " "; cout << endl;

    int sz = edge.size();
	InitMap(n, sz);
    for (auto [u, v]:edge) MakeMap(u, v);
}

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