제출 #1236315

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1236315		AmirAli_H1	항공 노선도 (JOI18_airline)	C++20	100 / 100	194 ms	31080 KiB

Alice

// In the name of Allah

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

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);

const int maxlg = 10, maxs = 1000;
const int maxn = (1 << maxlg) + 4;
static int valx[maxn], ind[maxn];

static int n, m;
static vector<pii> E, Ex;

static void upd_valx() {
	int j = 0;
	for (int i = 0; i < maxs; i++) {
		while (__builtin_popcount(j) <= 1) j++;
		valx[i] = j; ind[j] = i; j++;
	}
}

void Alice(int N, int M, int A[], int B[]) {
	upd_valx(); n = N; m = M;
	for (int i = 0; i < m; i++) E.pb(Mp(A[i], B[i]));
	for (auto f : E) Ex.pb(f);
	int vx = n + maxlg;
	Ex.pb(Mp(vx, vx + 1));
	for (int j = 0; j < maxlg; j++) Ex.pb(Mp(n + j, vx));
	for (int j = 1; j < maxlg; j++) Ex.pb(Mp(n + j - 1, n + j));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < maxlg; j++) {
			if (valx[i] & (1 << j)) {
				Ex.pb(Mp(i, n + j));
			}
		}
	}
	InitG(n + maxlg + 2, len(Ex));
	for (int i = 0; i < len(Ex); i++) MakeG(i, Ex[i].F, Ex[i].S);
}

Bob

// In the name of Allah

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

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);

const int maxlg = 10, maxs = 1000;
const int maxn = (1 << maxlg) + 4;
static int valx[maxn], ind[maxn];

static int n, m;
static vector<int> adj[maxn], ls;
static int M[maxn], D[maxn];
static int mark[maxn], Ax[maxn];
static vector<pii> E, Ex;

static void upd_valx() {
	int j = 0;
	for (int i = 0; i < maxs; i++) {
		while (__builtin_popcount(j) <= 1) j++;
		valx[i] = j; ind[j] = i; j++;
	}
}

void dfs(int v) {
	mark[v] = 1; ls.pb(v);
	for (int u : adj[v]) {
		if (!mark[u]) {
			dfs(u);
		}
	}
}

void Bob(int V, int U, int C[], int D[]) {
	upd_valx(); n = V; m = U;
	for (int i = 0; i < m; i++) {
		int u = C[i], v = D[i];
		adj[u].pb(v); adj[v].pb(u);
		Ex.pb(Mp(u, v));
	}

	int vx = -1;
	for (int i = 0; i < n; i++) {
		D[i] = len(adj[i]);
		if (len(adj[i]) == 1) vx = i;
	}
	int ux = adj[vx].back();
	for (int u : adj[ux]) {
		if (u == vx) continue;
		M[u] = 1;
	}

	for (int i = 0; i < n; i++) adj[i].clear();
	for (auto f : Ex) {
		int u = f.F, v = f.S;
		if (M[u] && M[v]) {
			adj[u].pb(v); adj[v].pb(u);
		}
	}
	int u1 = -1, u2 = -1;
	for (int i = 0; i < n; i++) {
		if (len(adj[i]) == 1) {
			if (u1 == -1) u1 = i;
			else u2 = i;
		}
	}
	if (D[u1] > D[u2]) dfs(u1);
	else dfs(u2);
	for (int i = 0; i < len(ls); i++) Ax[ls[i]] = (1 << i);

	for (int i = 0; i < n; i++) adj[i].clear();
	for (auto f : Ex) {
		int u = f.F, v = f.S;
		adj[u].pb(v); adj[v].pb(u);
	}
	for (int i = 0; i < n; i++) {
		if (i == vx || i == ux || M[i]) continue;
		for (int j : adj[i]) {
			if (!M[j]) continue;
			Ax[i] |= Ax[j];
		}
	}

	for (auto f : Ex) {
		int i = f.F, j = f.S;
		if (i == vx || i == ux || M[i]) continue;
		if (j == vx || j == ux || M[j]) continue;
		E.pb(Mp(ind[Ax[i]], ind[Ax[j]]));
	}
	InitMap(n - maxlg - 2, len(E));
	for (int i = 0; i < len(E); i++) MakeMap(E[i].F, E[i].S);
}

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