Submission #371609

#	Time	Username	Problem	Language	Result	Execution time	Memory
371609		RyoPham	Airline Route Map (JOI18_airline)	C++14	37 / 100	817 ms	35236 KiB

Alice

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

using namespace std;

#define sz(x) (int)x.size()
#define fi first
#define se second

typedef long long lli;
typedef pair<int, int> pii;

void Alice(int N, int M, int A[], int B[])
{
    const int logn = 10;

    if(N < 3)
    {
        InitG(N, M);
        if(M == 1)
            MakeG(0, 0, 1);
        return;
    }

    vector<pii> edges;
    for(int i = 0; i < M; ++i)
    {
        ++A[i]; ++B[i];
        edges.push_back(pii(A[i], B[i]));
    }
    for(int i = 1; i <= N; ++i)
    {
        edges.push_back(pii(i, N + logn + 1));
        for(int j = 0; j < logn; ++j)
            if(i >> j & 1) edges.push_back(pii(i, N + j + 1));
    }
    for(int j = 1; j < logn; ++j)
        edges.push_back(pii(N + j, N + j + 1));
    edges.push_back(pii(N + logn + 1, N + logn + 2));
    InitG(N + logn + 2, sz(edges));
    for(int i = 0; i < sz(edges); ++i)
        MakeG(i, edges[i].fi - 1, edges[i].se - 1);
}

Bob

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

using namespace std;

#define sz(x) (int)x.size()
#define fi first
#define se second

typedef long long lli;
typedef pair<int, int> pii;

const int maxn = 1505;

vector<int> gr[maxn];
bool origin[maxn], ok[maxn];

int mask[maxn];

void Bob(int V, int U, int C[], int D[])
{
    const int logn = 10;

    if(V < 3)
    {
        InitMap(V, U);
        if(U == 1)
            MakeMap(0, 1);
        return;
    }

    int N = V - logn - 2;

    vector<int> one_deg_vertices;
    for(int i = 0; i < U; ++i)
    {
        ++C[i]; ++D[i];
        gr[C[i]].push_back(D[i]);
        gr[D[i]].push_back(C[i]);
    }
    for(int i = 1; i <= V; ++i)
        if(sz(gr[i]) == 1) one_deg_vertices.push_back(i);
    assert(sz(one_deg_vertices) <= 2);
    int id_bit_10th = -1, min_deg = maxn;
    if(sz(one_deg_vertices) == 1)
    {
        int u = one_deg_vertices.back();
        u = gr[u].back();
        for(auto&v: gr[u])
            origin[v] = true;
        origin[u] = origin[one_deg_vertices.back()] = false;
        for(int i = 1; i <= V; ++i)
            if(!origin[i] && i != u && min_deg > sz(gr[i]))
            {
                min_deg = sz(gr[i]);
                id_bit_10th = i;
            }
    }
    else
    {
        int u = one_deg_vertices.back();
        u = gr[u].back();
        if(sz(gr[u]) != N + 1)
            swap(one_deg_vertices[0], one_deg_vertices[1]);
        id_bit_10th = one_deg_vertices[0];
        u = one_deg_vertices[1]; u = gr[u].back();
        for(auto&v: gr[u])
            origin[v] = true;
        origin[u] = origin[one_deg_vertices[1]] = false;
    }

    for(int i = logn - 1, j = id_bit_10th; i >= 0; --i)
    {
        int nj = -1;
        for(auto&k: gr[j])
        {
            if(origin[k]) mask[k] ^= (1 << i);
            else if(!ok[k])
            {
                assert(nj == -1);
                nj = k;
            }
        }
        ok[j] = true;
        j = nj;
        if(i > 0) assert(j != -1);
    }

    vector<pii> edges;
    for(int i = 0; i < U; ++i)
        if(origin[C[i]] && origin[D[i]])
            edges.push_back(pii(mask[C[i]] - 1, mask[D[i]] - 1));
    int M = sz(edges);

    InitMap(N, M);
    for(auto&e: edges)
        MakeMap(e.fi, e.se);
}

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