Submission #95826

#	Time	Username	Problem	Language	Result	Execution time	Memory
95826		Kastanda	Airline Route Map (JOI18_airline)	C++11	100 / 100	757 ms	30800 KiB

Alice

#include<bits/stdc++.h>
#include "Alicelib.h"
#define pb push_back
using namespace std;
void Alice(int N, int M, int A[], int B[])
{
    vector < pair < int , int > > E;
    for (int i = 0; i < M; i++)
        E.pb({A[i], B[i]});
    for (int i = 0; i < N; i++)
        for (int j = 0; j < 10; j++)
            if ((i >> j) & 1)
                E.pb({i, N + j});
    for (int j = 0; j < 9; j++)
        E.pb({N + j, N + j + 1});
    for (int i = 0; i < N + 10; i++)
        E.pb({i, N + 10});
    for (int j = 0; j < 10; j++)
        E.pb({N + 11, N + j});
    InitG(N + 12, (int)E.size());
    for (int i = 0; i < (int)E.size(); i++)
        MakeG(i, E[i].first, E[i].second);
    return ;
}

Bob

#include<bits/stdc++.h>
#include "Boblib.h"
#define pb push_back
using namespace std;
void Bob(int V, int U, int C[], int D[])
{
    int n_10 = -1;
    vector < bool > mark(V, 0);
    vector < vector < int > > Adj(V);
    vector < vector < bool > > is(V, vector < bool > (V, 0));
    for (int i = 0; i < U; i++)
        Adj[C[i]].pb(D[i]), Adj[D[i]].pb(C[i]),
        is[C[i]][D[i]] = is[D[i]][C[i]] = 1;
    for (int i = 0; i < V; i++)
        if ((int)Adj[i].size() == V - 2)
            n_10 = i;
    mark[n_10] = 1;
    for (int u : Adj[n_10])
        mark[u] = 1;
    int n_11 = -1;
    for (int i = 0; i < V; i++)
        if (!mark[i])
            n_11 = i;
    vector < int > bits, deg(10, 0);
    for (int u : Adj[n_11])
        bits.pb(u);
    for (int i = 0; i < 10; i++)
        for (int j = i + 1; j < 10; j++)
            if (is[bits[i]][bits[j]])
                deg[i] ++, deg[j] ++;
    int n_0 = -1;
    for (int i = 0; i < 10; i++)
        if (deg[i] == 1 && (n_0 == -1 || Adj[bits[n_0]].size() < Adj[bits[i]].size()))
            n_0 = i;
    vector < int > rbits(10, -1);
    rbits[0] = bits[n_0];
    bits[n_0] = -1;
    for (int i = 1; i < 10; i++)
    {
        int nxt = -1;
        for (int j = 0; j < 10; j++)
            if (bits[j] != -1 && is[rbits[i - 1]][bits[j]])
                nxt = j;
        rbits[i] = bits[nxt];
        bits[nxt] = -1;
    }
    mark = vector < bool > (V, 0);
    mark[n_10] = mark[n_11] = 1;
    for (int i = 0; i < 10; i++)
        mark[rbits[i]] = 1;
    vector < int > P(V, -1);
    for (int i = 0; i < V; i++)
        if (!mark[i])
        {
            int v = 0;
            for (int j = 0; j < 10; j++)
                if (is[i][rbits[j]])
                    v += (1 << j);
            P[i] = v;
        }
    vector < pair < int , int > > E;
    for (int i = 0; i < U; i++)
        if (!mark[C[i]] && !mark[D[i]])
            E.pb({P[C[i]], P[D[i]]});
    InitMap(V - 12, (int)E.size());
    for (int i = 0; i < (int)E.size(); i++)
        MakeMap(E[i].first, E[i].second);
}

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