Submission #1223503

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223503		Gray	Airline Route Map (JOI18_airline)	C++20	0 / 100	189 ms	26572 KiB

Alice

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

void Alice( int N, int M, int A[], int B[] ){
    vector<pair<ll, ll>> e;
    for (ll i=0; i<M; i++){
        e.push_back({A[i], B[i]});
    }

    ll offs=0;
    vector<ll> cnt(10);
    for (ll i=0; i<N; i++){
        for(ll j=0; j<10; j++) if (i&(1<<j)) cnt[j]++;
    }
    if (cnt[0]==cnt[9]){
        offs=1;
        // cout << "H" << endl;
    }

    for (ll i=offs; i<N+offs; i++){
        for (ll j=0; j<10; j++){
            if ((i&(1<<j))) e.push_back({i-offs, N+j});
        }
        e.push_back({i-offs, N+11});
    }
    for (ll j=0; j<10; j++) e.push_back({N+j, N+10});
    for (ll j=0; j<10; j++) e.push_back({N+j, N+11});
    for (ll j=1; j<10; j++) e.push_back({N+j, N+j-1});
    InitG(N+12, e.size());
    for (ll i=0; i<(ll)e.size(); i++){
        // cout << e[i].first << " " << e[i].second << endl;
        MakeG(i, e[i].first, e[i].second);
    }
}

Bob

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

void Bob( int V, int U, int C[], int D[] ){
    // cout << V << "-" << U << endl;
    vector<vector<ll>> A(V);
    ll n = V-12;
    ll offs=0;
    vector<ll> cnt(10);
    for (ll i=0; i<n; i++){
        for(ll j=0; j<10; j++) if (i&(1<<j)) cnt[j]++;
    }
    if (cnt[0]==cnt[9]){
        offs=1;
    }

    for (ll i=0; i<U; i++){
        A[C[i]].push_back(D[i]); A[D[i]].push_back(C[i]);
    }

    ll r1=-1, r2=-1; set<ll> usd;
    for (ll i=0; i<V; i++) usd.insert(i);
    for (ll i=0; i<V; i++){
        if ((ll)A[i].size()==V-2){
            r1=i; for (auto v:A[i]){
                usd.erase(v);
            }
            usd.erase(i);
            r2 = *usd.begin();
            break;
        }
    }
    assert(r1!=-1 and r2!=-1);

    set<ll> bits;
    for (auto v:A[r2]) bits.insert(v);

    // cout << A[r2].size() << endl;
    // for (auto ch:A[r2]) {
        // cout << ch << ": ";
    //     for (auto x:A[ch]){
            // cout << x << " ";
    //     }
        // cout << endl;
    // }
    // cout << endl;

    assert(A[r2].size()==10);
    vector<ll> bpos; ll cur=r1;
    // for (auto v:A[r2]) {
    //     cout << v << ": ";
    //     for (auto ch:A[v]) cout << ch << " ";
    //     cout << endl;
    // }
    // cout << endl;
    // cout << r1 << " " << r2 << endl;
    while (!bits.empty()){
        // cout << cur << endl;
        bool hp=0;
        for (auto v:A[cur]){
            if (bits.count(v)){
                cur=v; bpos.push_back(v);
                bits.erase(v); hp=1;break;
            }
        }
        if (!hp) break;
    }
    // cout << "AG" << endl;
    cur=bpos[0]; reverse(bpos.begin(), bpos.end());
    while (!bits.empty()){
        // cout << cur << endl;
        for (auto v:A[cur]){
            if (bits.count(v)){
                cur=v; bpos.push_back(v);
                bits.erase(v); break;
            }
        }
    }
    if (A[bpos[0]].size()!=cnt[0]){
        reverse(bpos.begin(), bpos.end());
    }
    // cout << "BP: ";
    // for (auto ch:bpos) cout << ch << " ";
    // cout << endl;
    map<ll, ll> mpid;
    for (ll i=0; i<10; i++){
        mpid[bpos[i]]=i; bits.insert(bpos[i]);
    }
    bits.insert(r1); bits.insert(r2);
    vector<vector<ll>> rA(n);
    map<ll, ll> ids;
    vector<pair<ll, ll>> e;
    for (ll i=0; i<U; i++){
        if (bits.count(C[i]) and bits.count(D[i])) continue;
        else{
            if (bits.count(C[i]) or bits.count(D[i])){
                if (bits.count(C[i]) and mpid.count(C[i])){
                    ids[D[i]]+=(1<<mpid[C[i]]);
                }else if(bits.count(D[i]) and mpid.count(D[i])){
                    ids[C[i]]+=(1<<mpid[D[i]]);
                }
            }else{
                e.push_back({C[i], D[i]});
            }
        }
    }
    // cout << "F: " << e.size() << endl;
    InitMap(n, e.size());
    for (auto [u, v]:e){
        // cout << ids[u]-offs << " " << ids[v]-offs << endl;
        MakeMap(ids[u]-offs, ids[v]-offs);
    }
}

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