제출 #1224589

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1224589		chaeryeong	Airline Route Map (JOI18_airline)	C++20	37 / 100	2527 ms	61112 KiB

Alice

#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;

//So it is obvious that you want to make log(n) extra nodes (10, 1 for each bit)
//But how will you determine these nodes
//You can think of using degrees to determine a node
//Add extra nodes X, Y. Connect X with all bit nodes, and connect Y with everything but X
//Y has maximum degree. You can determine X and Y. Then, you can determine the bits
//How to determine order of the bits? connect the bits in a chain. Now you just need to know 
//which endpoint of the chain is bit 0. For all 3 <= n <= 1000, bit 0 will have greater degree

void Alice (int n, int m, int A[], int B[]) {
	if (n == 1) {
		InitG(1, 0);
		return;
	}
	if (n == 2) {
		InitG(2, m);
		for (int i = 0; i < m; i++) {
			MakeG(i, A[i], B[i]);
		}
		return;
	}
	vector <pair <int, int>> ee;
	for (int i = 0; i < m; i++) {
		ee.push_back({A[i], B[i]});
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 10; j++) {
			if (i & (1 << j)) {
				ee.push_back({i, n + j});
			}
		}
	}
	for (int j = 0; j < 10; j++) {
		ee.push_back({n + j, n + 10});
	}
	for (int j = 0; j < n + 10; j++) {
		ee.push_back({j, n + 11});
	}
	for (int j = 0; j + 1 < 10; j++) {
		ee.push_back({n + j, n + j + 1});
	}
	for (auto &[x, y] : ee) {
		if (x > y) {
			swap(x, y);
		}
	}
	sort(ee.begin(), ee.end());
	ee.resize(unique(ee.begin(), ee.end()) - ee.begin());
	assert(ee.size() >= 0 && ee.size() <= (n + 12) * (n + 11) / 2);
	InitG(n + 12, ee.size());
	int cnt = 0;
	for (auto [x, y] : ee) {
		MakeG(cnt++, x, y);
	}
}

Bob

#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;

void Bob (int v, int u, int C[], int D[]) {
	if (v == 1) {
		InitMap(v, 0);
		return;
	}
	if (v == 2) {
		InitMap(v, u);
		if (u == 1) {
			MakeMap(0, 1);
		}
		return;
	}
	vector <int> deg(v, 0);
	for (int i = 0; i < u; i++) {
		deg[C[i]]++; deg[D[i]]++;
	}
	int Y = -1;
	for (int i = 0; i < v; i++) {
		if (Y == -1 || deg[i] > deg[Y]) {
			Y = i;
		}
	}
	set <int> adj[v];
	for (int i = 0; i < u; i++) {
		adj[C[i]].insert(D[i]);
		adj[D[i]].insert(C[i]);
	}
	int X = -1;
	for (int i = 0; i < v; i++) {
		if (i != Y && !adj[Y].count(i)) {
			X = i;
		}
	}
	set <int> ii;
	vector <int> path;
	int start = -1;
	for (auto i : adj[X]) {
		int d = 0;
		for (auto j : adj[X]) {
			d += adj[i].count(j);
		}
		if (d == 1) {
			start = i;
		}
	}
	while (true) {
		path.push_back(start);
		ii.insert(start);
		int nxt = -1;
		for (auto j : adj[start]) {
			if (!ii.count(j) && adj[X].count(j)) {
				nxt = j;
			}
		}
		if (nxt == -1) {
			break;
		}
		swap(start, nxt);
	}
	if (adj[path[0]].size() < adj[path[9]].size()) {
		reverse(path.begin(), path.end());
	}
	vector <pair <int, int>> ans;
	for (int i = 0; i < u; i++) {
		if (C[i] != X && C[i] != Y && !adj[X].count(C[i])) {
			if (D[i] != X && D[i] != Y && !adj[X].count(D[i])) {
				int a = 0;
				for (int j = 0; j < 10; j++) {
					if (adj[C[i]].count(path[j])) {
						a += 1 << j;
					}
				}
				int b = 0;
				for (int j = 0; j < 10; j++) {
					if (adj[D[i]].count(path[j])) {
						b += 1 << j;
					}
				}
				ans.push_back({a, b});
			}	
		}
	}
	InitMap(v - 12, ans.size());
	for (auto [x, y] : ans) {
		MakeMap(x, y);
	}
}

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