Submission #320184

#	Time	Username	Problem	Language	Result	Execution time	Memory
320184		thecodingwizard	Airline Route Map (JOI18_airline)	C++11	100 / 100	1126 ms	26576 KiB

Alice

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

void Alice( int N, int M, int A[], int B[] ){
    if (N == 1 && M == 0) {
        InitG(1, 0);
        return;
    }

    vector<int> adj[N+12];
    for (int i = 0; i < 9; i++) {
        adj[i].push_back(i+1);
    }
    for (int i = 12; i < N+12; i++) {
        adj[11].push_back(i);
        for (int j = 0; j < 10; j++) {
            if ((i-11) & (1 << j)) {
                adj[i].push_back(j);
            }
        }
    }
    for (int i = 0; i < M; i++) {
        adj[A[i]+12].push_back(B[i]+12);
    }
    adj[10].push_back(11); // special identifying node

    int edgeCt = 0;
    for (int i = 0; i < N+12; i++) edgeCt += adj[i].size();
    InitG(N+12, edgeCt);
    int ctr = 0;
    for (int i = 0; i < N+12; i++) {
        for (int j : adj[i]) {
            MakeG(ctr++, i, j);
        }
    }
}

Bob

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

void Bob( int V, int U, int C[], int D[] ){
    if (V == 1 && U == 0) {
        InitMap(1, 0);
        return;
    }
    vector<int> adj[V];
    for (int i = 0; i < U; i++) {
        adj[C[i]].push_back(D[i]);
        adj[D[i]].push_back(C[i]);
    }
    map<int, int> realID;
    int excludeBits = -1;
    for (int i = 0; i < V; i++) {
        if (adj[i].size() == 1) {
            if ((int)adj[adj[i][0]].size() == V-11) {
                assert(excludeBits == -1);
                excludeBits = adj[i][0];
                realID[i] = -1;
            }
        }
    }
    assert(excludeBits != -1);
    set<int> bitNodesSet;
    for (int i = 0; i < V; i++) {
        bitNodesSet.insert(i);
    }
    for (int j : adj[excludeBits]) bitNodesSet.erase(j);
    bitNodesSet.erase(excludeBits);
    assert(bitNodesSet.size() == 10);
    int largestBit = *bitNodesSet.begin();
    for (int x : bitNodesSet) {
        if (adj[largestBit].size() > adj[x].size()) largestBit = x;
    }
    vector<int> bitNodes;
    int cur = largestBit;
    while (cur != -1) {
        bitNodes.push_back(cur);
        int nxt = -1;
        for (int v : adj[cur]) {
            if (bitNodesSet.count(v) && find(bitNodes.begin(), bitNodes.end(), v) == bitNodes.end()) {
                assert(nxt == -1);
                nxt = v;
            }
        }
        cur = nxt;
    }
    assert(bitNodes.size() == 10);
    reverse(bitNodes.begin(), bitNodes.end());
    realID[excludeBits] = -1;
    for (int x : bitNodes) realID[x] = -1;
    for (int i = 0; i < V; i++) {
        if (realID[i] != -1) {
            int v = 0;
            for (int j : adj[i]) {
                auto it = find(bitNodes.begin(), bitNodes.end(), j);
                if (it == bitNodes.end()) continue;
                int val = it - bitNodes.begin();
                v |= (1 << val);
            }
            realID[i] = v-1;
            assert(0 <= v-1 && v-1 < V-12);
        }
    }
    vector<int> realAdj[V-12];
    for (int i = 0; i < V; i++) {
        if (realID[i] != -1) {
            for (int j : adj[i]) {
                if (realID[j] == -1) continue;
                int a = realID[i], b = realID[j];
                if (a < b) {
                    realAdj[a].push_back(b);
                }
            }
        }
    }
    int edgeCt = 0;
    for (int i = 0; i < V-12; i++) edgeCt += realAdj[i].size();
	InitMap( V-12, edgeCt );
    for (int i = 0; i < V-12; i++) {
        for (int j : realAdj[i]) {
            MakeMap(i, j);
        }
    }
}

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