Submission #250931

#	Time	Username	Problem	Language	Result	Execution time	Memory
250931		imeimi2000	Airline Route Map (JOI18_airline)	C++17	100 / 100	854 ms	25836 KiB

Alice

#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include <vector>
 
using namespace std;
typedef pair<int, int> pii;
 
void Alice(int N, int M, int A[], int B[]) {
    vector<pii> es;
	for (int i = 0; i < N + 10; ++i) {
        es.emplace_back(i, N + 10);
	}
	for (int i = 0; i < 10; ++i) {
        es.emplace_back(N + i, N + 11);
	}
	for (int i = 0; i < 9; ++i) {
        es.emplace_back(N + i, N + i + 1);
	}
	for (int i = 0; i < N; ++i) {
        for (int j = 0; j < 10; ++j) {
            if ((i >> j) & 1) es.emplace_back(i, N + j);
        }
	}
	InitG(N + 12, M + es.size());
	int j = 0;
	for (int i = 0; i < M; ++i) MakeG(j++, A[i], B[i]);
	for (pii i : es) MakeG(j++, i.first, i.second);
}

Bob

#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include <vector>
 
using namespace std;
typedef pair<int, int> pii;
 
vector<int> edge[1012];
vector<int> line[1012];
int ch[1012];
int tr[1012];
void Bob(int V, int U, int C[], int D[]){
    for (int i = 0; i < U; ++i) {
        edge[C[i]].push_back(D[i]);
        edge[D[i]].push_back(C[i]);
    }
    int x = -1;
    for (int i = 0; i < V; ++i) {
        if (edge[i].size() == V - 2) {
            x = i;
            break;
        }
    }
    int y = -1;
    for (int i : edge[x]) {
        ch[i] = 1;
    }
    for (int i = 0; i < V; ++i) {
        if (i == x) continue;
        if (ch[i]) {
            ch[i] = 0;
            continue;
        }
        y = i;
    }
    for (int i : edge[y]) {
        for (int j : edge[i]) {
            if (ch[j]) {
                line[i].push_back(j);
                line[j].push_back(i);
            }
        }
        ch[i] = 1;
    }
    int s = -1;
    for (int i : edge[y]) {
        if (line[i].size() > 1) continue;
        if (s != -1 && edge[i].size() < edge[s].size()) continue;
        s = i;
    }
    for (int i = 0, t = s, p = -1; i < 10; ++i) {
        if (i) {
            for (int j : line[t]) {
                if (j == p) continue;
                p = t;
                t = j;
                break;
            }
        }
        for (int j : edge[t]) {
            if (j == x || j == y) continue;
            if (ch[j]) continue;
            tr[j] |= (1 << i);
        }
    }
    ch[x] = ch[y] = 1;
    
    vector<pii> es;
    for (int i = 0; i < U; ++i) {
        if (ch[C[i]] || ch[D[i]]) continue;
        es.emplace_back(tr[C[i]], tr[D[i]]);
    }
    InitMap(V - 12, es.size());
    for (pii i : es) {
        MakeMap(i.first, i.second);
    }
}

Compilation message (stderr)

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:20:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (edge[i].size() == V - 2) {
             ~~~~~~~~~~~~~~~^~~~~~~~

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