Submission #644082

#	Time	Username	Problem	Language	Result	Execution time	Memory
644082		valerikk	Airline Route Map (JOI18_airline)	C++17	0 / 100	695 ms	30556 KiB

Alice

#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include <vector>

using namespace std;

void Alice(int N, int M, int A[], int B[]) {
    vector<pair<int, int>> edges;

    for (int i = 0; i < M; ++i) {
        edges.push_back({A[i], B[i]});
    }
    edges.push_back({N + 2, N});
    edges.push_back({N + 11, N + 1});
    for (int i = 0; i < 9; ++i) {
        edges.push_back({N + 2 + i, N + 3 + i});
    }

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < 10; ++j) {
            if (((i + 1) >> j) & 1)
                edges.push_back({i, N + 2 + j});
        }
    }

    InitG(N + 12, edges.size());

    for (int i = 0; i < edges.size(); ++i) {
        MakeG(i, edges[i].first, edges[i].second);
    }
}   

Bob

#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define MAXV 1021

vector<int> in[MAXV], out[MAXV];
int val[MAXV];
int id[MAXV];

void Bob(int V, int U, int C[], int D[]) {
    for (int i = 0; i < U; ++i) {
        in[D[i]].push_back(C[i]);
        out[C[i]].push_back(D[i]);
    }

    int s0 = -1, t0 = -1;
    
    for (int i = 0; i < V; ++i) {
        if (out[i].empty()) {
            if (s0 == -1) {
                s0 = i;
            } else {
                assert(t0 == -1);
                t0 = i;
            }
        }
    }

    assert(in[s0].size() == 1);
    assert(in[t0].size() == 1);

    int s = in[s0][0];
    int t = in[t0][0];

    if (out[s].size() != 2){
        swap(s, t);
        swap(s0, t0);
    }

    for (int i = 0; i < V; ++i) {
        val[i] = -1;
    }

    val[s0] = val[t0] = -2;

    for (int v = s, i = 0; i < 10; ++i) {
        val[v] = i;

        if (v == t)
            break;

        for (int u : out[v]) {
            if (u != s0) {
                v = u;
                break;
            }
        }
    }

    for (int i = 0; i < V; ++i) {
        if (val[i] == -1) {
            id[i] = -1;
            for (int j : out[i]) {
                if (val[j] >= 0) {
                    id[i] += 1 << val[j];
                }
            }
        }
    }

    vector<pair<int, int>> edges;

    for (int i = 0; i < U; ++i) {
        if (val[C[i]] == -1 && val[D[i]] == -1) {
            edges.push_back({id[C[i]], id[D[i]]});
        }
    }

    InitMap(V - 12, edges.size());

    for (int i = 0; i < edges.size(); ++i) {
        MakeMap(edges[i].first, edges[i].second);
    }

}

Compilation message (stderr)

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

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

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