Submission #46420

#	Time	Username	Problem	Language	Result	Execution time	Memory
46420		SpaimaCarpatilor	Airline Route Map (JOI18_airline)	C++17	100 / 100	730 ms	31032 KiB

Alice

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

using namespace std;

static const int K = 10;
static vector < pair < int, int > > edges;
void Alice (int N, int M, int A[], int B[])
{
    for (int i=0; i<M; i++)
        edges.push_back ({A[i] + 1, B[i] + 1});
    int x = N + K + 1, y = N + K + 2;
    for (int i=1; i<x; i++)
        edges.push_back ({i, y});
    for (int i=N + 1; i<=N + K; i++)
        edges.push_back ({i, x});
    for (int i=1; i<=N; i++)
        for (int j=0; j<K; j++)
            if (i & (1 << j))
                edges.push_back ({i, N + 1 + j});
    for (int i=N + 1; i<N + K; i++)
        edges.push_back ({i, i + 1});
    InitG (N + K + 2, edges.size ());
    int pos = 0;
    for (auto e : edges)
    {
        //printf ("%d %d\n", e.first, e.second);
        MakeG (pos ++, e.first - 1, e.second - 1);
    }
}

Bob

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

using namespace std;

static const int K = 10;
static int prv[1109], nxt[1109], sz[1109], bitPos[1109], p[1109];
static bool ap[1109][1109], isGraph[1109];

void detChain (int x, int y, int V, vector < int > &chain)
{
    for (int i=1; i<=V; i++)
        if (ap[x][i])
            chain.push_back (i);
    for (auto i1 : chain)
        for (auto i2 : chain)
            if (ap[i1][i2])
            {
                if (prv[i1] == 0) prv[i1] = i2;
                else nxt[i1] = i2;
            }
    int end1 = 0, end2 = 0;
    for (auto i : chain)
        if (nxt[i] == 0)
        {
            if (end1 == 0) end1 = i;
            else end2 = i;
        }
    if (sz[end2] > sz[end1]) swap (end1, end2);
    chain.clear ();
    chain.push_back (end1), chain.push_back (prv[end1]);
    int pi1 = end1, pi = prv[end1];
    while (nxt[pi] != 0)
    {
        int npi1 = pi, npi = prv[pi] ^ nxt[pi] ^ pi1;
        pi1 = npi1, pi = npi, chain.push_back (pi);
    }
}

void Bob (int V, int U, int C[], int D[])
{
    for (int i=0; i<U; i++)
        C[i] ++, D[i] ++,
        ap[C[i]][D[i]] = ap[D[i]][C[i]] = 1,
        sz[C[i]] ++, sz[D[i]] ++;
//        printf ("%d %d\n", C[i], D[i]);
    int maxDeg = -1, y = -1, x = -1;
    for (int i=1; i<=V; i++)
        if (sz[i] > maxDeg)
            maxDeg = sz[i], y = i;
    assert (maxDeg == V - 2);
    for (int i=1; i<=V; i++)
        if (ap[i][y] == 0 && i != y)
            x = i;
    vector < int > chain;
    detChain (x, y, V, chain);
/*    for (auto it : chain)
        printf ("%d ", it);
    printf ("\n");*/
    assert (chain.size () == K);
    for (int i=1; i<=V; i++)
        if (i != x && i != y)
            isGraph[i] = 1;
    for (auto it : chain)
        isGraph[it] = 0;
/*    for (int i=1; i<=V; i++)
        if (isGraph[i])
            printf ("%d ", i);
    printf ("\n");*/
    for (int i=0; i<K; i++)
        bitPos[chain[i]] = i;
    for (int i=1; i<=V; i++)
        for (int j=1; j<=V; j++)
            if (ap[i][j] == 1 && isGraph[i] == 1 && isGraph[j] == 0 && j != x && j != y)
                p[i] |= 1 << bitPos[j];
/*    for (int i=1; i<=V; i++)
        if (p[i] != 0)
            printf ("%d -> %d\n", i, p[i]);*/
    vector < pair < int, int > > edges;
    for (int i=1; i<=V; i++)
        for (int j=i + 1; j<=V; j++)
            if (isGraph[i] == 1 && isGraph[j] == 1 && ap[i][j] == 1)
                edges.push_back ({p[i], p[j]});
	InitMap (V - K - 2, edges.size ());
	for (auto e : edges)
        MakeMap (e.first - 1, e.second - 1);
}

Compilation message (stderr)

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:80:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for (int i=1; i<=V; i++)
     ^~~
Bob.cpp:84:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  InitMap (V - K - 2, edges.size ());
  ^~~~~~~

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