제출 #1224597

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1224597		chaeryeong	항공 노선도 (JOI18_airline)	C++20	100 / 100	257 ms	23224 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;
		}
	}
	vector <int> adj[v];
	for (int i = 0; i < v; i++) {
		adj[i] = vector <int> (v, 0);
	}
	for (int i = 0; i < u; i++) {
		adj[C[i]][D[i]] = adj[D[i]][C[i]] = 1;
	}
	int X = -1;
	for (int i = 0; i < v; i++) {
		if (i != Y && !adj[Y][i]) {
			X = i;
		}
	}
	vector <int> ii(v, 0);
	vector <int> path;
	int start = -1;
	for (int i = 0; i < v; i++) {
		if (adj[X][i]) {
			int d = 0;
			for (int j = 0; j < v; j++) {
				if (adj[X][j]) {
					d += adj[i][j];
				}
			}
			if (d == 1) {
				start = i;
			}
		}
	}
	while (true) {
		assert(start != -1);
		path.push_back(start);
		ii[start] = 1;
		int nxt = -1;
		for (int j = 0; j < v; j++) {
			if (adj[start][j]) {
				if (!ii[j] && adj[X][j]) {
					nxt = j;
				}
			}
		}
		if (nxt == -1) {
			break;
		}
		swap(start, nxt);
	}
	int cnt1 = 0, cnt2 = 0;
	for (int i = 0; i < v; i++) {
		cnt1 += adj[path[0]][i];
		cnt2 += adj[path[9]][i];
	}
	if (cnt1 < cnt2) {
		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][C[i]]) {
			if (D[i] != X && D[i] != Y && !adj[X][D[i]]) {
				int a = 0;
				for (int j = 0; j < 10; j++) {
					if (adj[C[i]][path[j]]) {
						a += 1 << j;
					}
				}
				int b = 0;
				for (int j = 0; j < 10; j++) {
					if (adj[D[i]][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: 63 / 63