Submission #47807

#	Time	Username	Problem	Language	Result	Execution time	Memory
47807		qoo2p5	Airline Route Map (JOI18_airline)	C++17	100 / 100	827 ms	30720 KiB

Alice

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

using namespace std;

typedef long long ll;

const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;

#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back

static bool test(int mask, int bit) {
    return mask & (1 << bit);
}

void Alice(int n, int m, int a[], int b[]) {
    vector<pair<int, int>> e;
    
    rep(i, 0, m) {
        e.pb({a[i], b[i]});
    }
    rep(i, 0, n + 12) {
        if (i != n && i != n + 1) {
            e.pb({n, i});
        }
    }
    rep(i, n + 2, n + 12) {
        e.pb({n + 1, i});
    }
    rep(i, n + 2, n + 11) {
        e.pb({i, i + 1});
    }
    rep(i, 0, n) {
        rep(bit, 0, 10) {
            if (test(i, bit)) {
                e.pb({i, n + 2 + bit});
            }
        }
    }
    
    InitG(n + 12, sz(e));
    rep(i, 0, sz(e)) {
        auto it = e[i];
        MakeG(i, it.first, it.second);
    }
}

Bob

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

using namespace std;

typedef long long ll;

const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;

#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back

static bool test(int mask, int bit) {
    return mask & (1 << bit);
}

void Bob(int V, int U, int C[], int D[]) {
    int n = V - 12;
    vector<vector<int>> g(V);
    rep(i, 0, U) {
        g[C[i]].pb(D[i]);
        g[D[i]].pb(C[i]);
    }
    rep(i, 0, V) {
        sort(all(g[i]));
    }
    int C1 = -1;
    rep(i, 0, V) {
        if (sz(g[i]) == n + 10) {
            assert(C1 == -1);
            C1 = i;
        }
    }
    assert(C1 != -1);
    
    int C2 = -1;
    rep(i, 0, V) {
        if (i == C1) {
            continue;
        }
        if (!binary_search(all(g[C1]), i)) {
            assert(C2 == -1);
            C2 = i;
        }
    }
    assert(C2 != -1);
    
    vector<int> cool;
    for (int i : g[C2]) {
        cool.pb(i);
    }
    sort(all(cool));
    assert(sz(cool) == 10);
    
    int v = cool.back();
    int prv = -1;
    while (1) {
        int to = -1;
        for (int u : g[v]) {
            if (!binary_search(all(cool), u) || u == prv) {
                continue;
            }
            to = u;
        }
        if (to == -1) {
            break;
        }
        prv = v;
        v = to;
    }
    
    vector<int> seq;
    seq.pb(v);
    prv = -1;
    while (1) {
        int to = -1;
        for (int u : g[v]) {
            if (!binary_search(all(cool), u) || u == prv) {
                continue;
            }
            to = u;
        }
        if (to == -1) {
            break;
        }
        prv = v;
        v = to;
        seq.pb(v);
    }
    
    assert(sz(seq) == 10);
    vector<bool> our(V, 1);
    our[C1] = 0;
    our[C2] = 0;
    for (int v : seq) {
        our[v] = 0;
    }
    
    int cnt_our = 0;
    for (bool i : our) {
        cnt_our += i;
    }
    assert(cnt_our == n);
    
    rep(iter, 0, 2) {
        vector<int> wow(V, -1);
        rep(i, 0, 10) {
            wow[seq[i]] = i;
        }
        
        bool ok = 1;
        
        rep(v, 0, V) {
            if (!our[v]) {
                continue;
            }
            int id = 0;
            for (int u : g[v]) {
                if (wow[u] != -1) {
                    id |= (1 << wow[u]);
                }
            }
            if (id >= n) {
                ok = 0;
                break;
            }
        }
        
        if (iter == 1) {
            assert(ok);
        }
        
        if (ok) {
            break;
        }
        
        reverse(all(seq));
    }
    
    
    vector<int> wow(V, -1);
    rep(i, 0, 10) {
        wow[seq[i]] = i;
    }
    
    vector<int> id(V, -1);    
    rep(v, 0, V) {
        if (!our[v]) {
            continue;
        }
        id[v] = 0;
        for (int u : g[v]) {
            if (wow[u] != -1) {
                id[v] |= (1 << wow[u]);
            }
        }
    }
    
    vector<pair<int, int>> adj;
    rep(i, 0, V) {
        for (int j : g[i]) {
            int u = id[i];
            int v = id[j];
            if (u == -1 || v == -1) {
                continue;
            }
            if (u < v) {
                adj.pb({u, v});
            }
        }
    }
    
    InitMap(n, sz(adj));
    for (auto &it : adj) {
        MakeMap(it.first, it.second);
    }
}

Compilation message (stderr)

Bob.cpp:20:13: warning: 'bool test(int, int)' defined but not used [-Wunused-function]
 static bool test(int mask, int bit) {
             ^~~~

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