Submission #1270790

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270790		tvgk	Airline Route Map (JOI18_airline)	C++20	100 / 100	158 ms	31144 KiB

Alice

#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 1e3 + 20;

vector<ii> ed;

void Alice(int n, int m, int a[], int b[])
{
	for (int i = 0; i < m; i++)
        ed.push_back({a[i], b[i]});

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

        if (j)
            ed.push_back({n + j, n + j - 1});
    }

    for (int i = 0; i < n + 10; i++)
        ed.push_back({n + 11, i});

    InitG(n + 12, ed.size());
    m = 0;
    for (ii i : ed)
        MakeG(m++, i.fi, i.se);
}

Bob

#include "Boblib.h"

#include <algorithm>
#include <vector>
#include <cassert>

using namespace std;

namespace {
vector<int> graph[2000];
bool mark[2000];
int id[2000];
}

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

	pair<int, int> mxdeg{ -1, -1 };
	for (int i = 0; i < V; ++i) mxdeg = max(mxdeg, { graph[i].size(), i });

	int s = mxdeg.second;
	int w = V * (V - 1) / 2 - s;
	for (int u : graph[s]) w -= u;

	for (int i = 0; i < V; ++i) mark[i] = false;
	for (int u : graph[w]) mark[u] = true;

	vector<int> marker;
	int p = -1, ori = -1;

	for (int i = 0; i < V; ++i) if (mark[i]) {
		int d = 0, nx = 0;
		for (int j : graph[i]) if (mark[j]) {
			++d;
			nx = j;
		}

		if (d == 1) {
			p = nx;
			ori = i;
			break;
		}
	}

	assert(p != -1);

	marker.push_back(ori);

	for (;;) {
		marker.push_back(p);
		bool found = false;
		for (int q : graph[p]) if (mark[q] && q != ori) {
			ori = p;
			p = q;
			found = true;
			break;
		}
		if (!found) break;
	}

	if (graph[marker[0]].size() < graph[marker[marker.size() - 1]].size()) {
		reverse(marker.begin(), marker.end());
	}

	for (int i = 0; i < V; ++i) id[i] = 0;
	for (int i = 0; i < marker.size(); ++i) {
		for (int j : graph[marker[i]]) {
			id[j] |= 1 << i;
		}
	}

	mark[s] = mark[w] = true;
	vector<pair<int, int> > ans;
	for (int i = 0; i < V; ++i) if (!mark[i]) {
		for (int j : graph[i]) if (i < j && !mark[j]) {
			ans.push_back({ id[i], id[j] });
		}
	}
	InitMap(V - 12, ans.size());
	for (auto e : ans) MakeMap(e.first, e.second);
}

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