Submission #991807

#	Time	Username	Problem	Language	Result	Execution time	Memory
991807		danikoynov	Airline Route Map (JOI18_airline)	C++14	69 / 100	415 ms	72492 KiB

Alice

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

using namespace std;

const int maxn = 2e3 + 10;
const int maxbit = 11;
const int fict = 12;
/**
from 0 to N - 1 : normal vertexes
from N to N + maxbit - 1 : binary powers
from N + maxbit to N + maxbit + fict - 1 : fictitious vertexes
vertex N + maxbit is connected to all except the binary powers

*/
void Alice( int N, int M, int A[], int B[] )
{
    if (N == 1 && M == 0)
    {
        InitG(1, 0);
        return;
    }
    vector < pair < int, int > > edges;
    for (int i = 0; i < M; i ++)
        edges.push_back({A[i], B[i]});
    for (int i = 0; i < N; i ++)
    {
        for (int bit = 0; bit < maxbit; bit ++)
        {
            if ((i & (1 << bit)) > 0)
                edges.push_back({i, N + bit});
        }
    }
    for (int i = 0; i < N; i ++)
        edges.push_back({N + maxbit, i});
    for (int i = N + maxbit + 1; i < N + maxbit + fict; i ++)
        edges.push_back({N + maxbit, i});


    for (int i = N + 1; i < N + maxbit; i ++)
        edges.push_back({i - 1, i});

    InitG(N + maxbit + fict, edges.size());
    int cnt = 0;
    for (pair < int, int > cur : edges)
    {
        MakeG(cnt ++, cur.first, cur.second);
    }
}

Bob

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

using namespace std;

const int MAXN = 2e3 + 10;
struct edge
{
    int v, u;

    edge(int _v = 0, int _u = 0)
    {
        v = _v;
        u = _u;
    }
}edges[MAXN * MAXN];

int deg[MAXN], non_bin[MAXN];
vector < int > adj[MAXN];
int value[MAXN], ridx[MAXN];
vector < int > path;
void dfs(int v, int p)
{
    path.push_back(v);
    for (int u : adj[v])
    {
        if (u == p)
            continue;
        dfs(u, v);
    }
}

const int MAXBIT = 11;
const int FICT = 12;

void Bob( int V, int U, int C[], int D[] )
{
    if (V == 1 && U == 0)
    {
        InitMap(1, 0);
        return;
    }
    for (int i = 0; i < U; i ++)
    {
        edges[i] = edge(C[i], D[i]);
        deg[C[i]] ++;
        deg[D[i]] ++;
    }

    int mx = 0;
    for (int i = 0; i < V; i ++)
        if (deg[i] > deg[mx])
        mx = i;


    for (int i = 0; i < U; i ++)
    {
        if (C[i] == mx)
            non_bin[D[i]] = 1;
        else
        if (D[i] == mx)
            non_bin[C[i]] = 1;
    }

    for (int i = 0; i < U; i ++)
    {
        if (non_bin[C[i]] || non_bin[D[i]])
            continue;

        adj[C[i]].push_back(D[i]);
        adj[D[i]].push_back(C[i]);
    }

    int ver = 0;
    for (int i = 0; i < V; i ++)
    {
        if (non_bin[i] == 0 && deg[i] == 1)
            ver = i;
    }

    dfs(ver, - 1);
    reverse(path.begin(), path.end());

    for (int i = 0; i < V; i ++)
        adj[i].clear();
    for (int i = 0; i < U; i ++)
    {
                adj[C[i]].push_back(D[i]);
        adj[D[i]].push_back(C[i]);
    }
    for (int i = 0; i < path.size(); i ++)
    {
        value[path[i]] = (1 << i);
    }

    vector < pair < int, int > > ls;
    for (int i = 0; i < V; i ++)
    {
        for (int u : adj[i])
        {
            if (non_bin[u] == 0)
            ridx[i] += value[u];
        }
    }


    for (int i = 0; i < U; i ++)
    {
        if (C[i] == ver || D[i] == ver)
            continue;
        if (non_bin[C[i]] == 0 || non_bin[D[i]] == 0)
            continue;
        ls.push_back({ridx[C[i]], ridx[D[i]]});

    }

    InitMap(V - FICT - MAXBIT, ls.size());
    for (pair < int, int > cur : ls)
        MakeMap(cur.first, cur.second);




}

Compilation message (stderr)

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:93:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for (int i = 0; i < path.size(); i ++)
      |                     ~~^~~~~~~~~~~~~

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