제출 #62958

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
62958		kingpig9	항공 노선도 (JOI18_airline)	C++11	0 / 100	550 ms	34184 KiB

Alice

#include "Alicelib.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

static bool exist1[1111];
static int nedge;
static pii edges[1111111];

void Alice (int N, int M, int A[], int B[]) {
	for (int i = 0; i < M; i++) {
		if (A[i] > B[i]) {
			swap(A[i], B[i]);
		}
		if (B[i] == A[i] + 1) {
			exist1[A[i]] = true;
		}
		edges[nedge++] = pii(A[i], B[i]);
	}

	for (int i = 0; i < N - 1; i++) {
		if (!exist1[i]) {
			edges[nedge++] = pii(i, i + 1);
			edges[nedge++] = pii(i, N);
		}
	}
	edges[nedge++] = pii(N - 1, N);

	InitG(N + 1, nedge);
	for (int i = 0; i < nedge; i++) {
		MakeG(i, edges[i].fi, edges[i].se);
	}
}

Bob

#include "Boblib.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

static int adj[1111][1111];
static int deg[1111];
static int indeg[1111];
static int ind[1111];
static pii ans[1111111];
static int anse;

void Bob (int N, int M, int C[], int D[]) {
	//toposort!

	for (int i = 0; i < M; i++) {
		adj[C[i]][deg[C[i]]++] = D[i];
		indeg[D[i]]++;
	}

	//toposort
	vector<int> topo = vector<int> ();
	stack<int> stk = stack<int> ();

	for (int i = 0; i < N; i++) {
		if (indeg[i] == 0) {
			stk.push(i);
		}
	}

	while (!stk.empty()) {
		int x = stk.top();
		stk.pop();
		ind[x] = topo.size();
		topo.push_back(x);

		for (int i = 0; i < deg[x]; i++) {
			int y = adj[x][i];
			if (--indeg[y] == 0) {
				stk.push(y);
			}
		}
	}

	int last = topo.back();
	for (int x : topo) {
		if (x == last) {
			break;
		}

		bool existlast = false;
		for (int i = 0; i < deg[x]; i++) {
			int y = adj[x][i];
			if (y == last) {
				existlast = true;
			} else if (y != topo[ind[x] + 1]) {
				ans[anse++] = pii(ind[x], ind[y]);
			}
		}

		if (!existlast) {
			//then x, x + 1
			ans[anse++] = pii(ind[x], ind[x] + 1);
		}
	}

	//FINAL ANSWERS!
	InitMap(N - 1, anse);
	for (int i = 0; i < anse; i++) {
		pii p = ans[i];
		MakeMap(p.fi, p.se);
	}
}

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