Submission #105573

#	Time	Username	Problem	Language	Result	Execution time	Memory
105573		szawinis	Airline Route Map (JOI18_airline)	C++17	100 / 100	845 ms	31048 KiB

Alice

#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include <vector>
#include <utility>
#include <iostream>
const int K = 10;

void Alice( int N, int M, int A[], int B[] ){
    if(N == 1) {
        InitG(N, M);
        return;
    }
    if(N == 2) {
        InitG(N, M);
        if(M) MakeG(0, 0, 1);
        return;
    }
	std::vector<std::pair<int, int> > edges;
	for(int i = 0; i < M; i++) {
		edges.emplace_back(A[i], B[i]); // original graph
	}
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < K; j++) {
			if(!((i + 1) >> j & 1)) continue; // make graph 1-indexed, so connect to corresponding nodes
			edges.emplace_back(i, N + j); // links between bit vertices and origianl vertices
		}
	}
	for(int j = 0; j < K - 1; j++) edges.emplace_back(N + j, N + j + 1); // links between bit vertices
	for(int i = 0; i < N; i++) {
		edges.emplace_back(i, N + K); // N + 10 is the special vertex
	}
	edges.emplace_back(N + K, N + K + 1); // N + 11 is the one-degree vertex
	int curr_idx = 0;
	InitG(N + K + 2, edges.size());
//    for(auto p: edges) std::cerr << p.first << ' ' << p.second << std::endl;
	for(auto p: edges) MakeG(curr_idx++, p.first, p.second);
}

Bob

#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
const int K = 10;

void Bob(int N, int M, int A[], int B[]) {
    if(N == 1) {
        InitMap(N, M);
        return;
    }
    if(N == 2) {
        InitMap(N, M);
        for(int i = 0; i < M; i++) MakeMap(A[i], B[i]);
        return;
    }
    std::vector<int> g[N];
    for(int i = 0; i < M; i++) {
        g[A[i]].push_back(B[i]);
        g[B[i]].push_back(A[i]);
//        std::cerr << A[i] << ' ' << B[i] << ' ' << std::endl;
    }

    //find special vertex
    std::vector<int> deg1;
    for(int i = 0; i < N; i++) if(g[i].size() == 1) deg1.push_back(i);
    assert(deg1.size() <= 2);
    int very_special_vertex = deg1[0]; // vertex of degree 1 that points to the special vertex
    int special_vertex = g[deg1[0]][0];
    if(deg1.size() == 2) {
        if(g[special_vertex].size() != N - K - 1) {
            very_special_vertex = deg1[1];
            special_vertex = g[deg1[1]][0];
        }
    }
//    std::cerr << "specials " << very_special_vertex << ' ' << special_vertex << std::endl;
//    std::cerr << "bit_vertices " << std::endl;

    //find bit vertices
    std::vector<int> bit_vertices;
    std::vector<bool> is_bit_vertex(N);
    for(int i = 0; i < N; i++) if(i != special_vertex) {
        if(std::find(g[i].begin(), g[i].end(), special_vertex) == g[i].end()) {
            bit_vertices.push_back(i);
            is_bit_vertex[i] = true;
        }
    }
    assert(bit_vertices.size() == K);

    int mx_bit_vertex = *min_element(bit_vertices.begin(), bit_vertices.end(), [&] (int i, int j) { return g[i].size() < g[j].size(); });
    std::vector<int> vals(N);
    for(int ord = K - 1, curr = mx_bit_vertex; ord >= 0; ord--) {
//        std::cerr << curr << ' ' << ord << std::endl;
        for(int v: g[curr]) {
            assert(v != very_special_vertex && v != special_vertex);
            if(is_bit_vertex[v]) continue;
            vals[v] |= 1 << ord;
        }

        for(int v: g[curr]) {
            if(is_bit_vertex[v]) {
                g[v].erase(std::find(g[v].begin(), g[v].end(), curr));
                curr = v;
                break;
            }
        }
    }

    auto in_org_graph = [&] (int v) -> bool { return v != very_special_vertex && v != special_vertex && !is_bit_vertex[v]; };
    std::vector<std::pair<int,int> > ans;
    for(int i = 0; i < M; i++) {
        if(in_org_graph(A[i]) && in_org_graph(B[i])) ans.emplace_back(vals[A[i]] - 1, vals[B[i]] - 1);
    }
    InitMap(N - K - 2, ans.size());
//    for(auto p: ans) std::cerr << p.first << ' ' << p.second << std::endl;
    for(auto p: ans) MakeMap(p.first, p.second);
}

Compilation message (stderr)

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:33:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(g[special_vertex].size() != N - K - 1) {
            ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

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