Submission #410609

#	Time	Username	Problem	Language	Result	Execution time	Memory
410609		Namnamseo	Airline Route Map (JOI18_airline)	C++17	100 / 100	815 ms	26264 KiB

Alice

#include <vector>
#include <utility>
using namespace std;
using pp=pair<int,int>;

void InitG(int, int);
void MakeG(int, int, int);

namespace ALICE {
vector<pp> e;

void Alice(int n, int m, int A[], int B[]) {
	const int
		bvo = n,
		X = bvo+10,
		Y = X+1;
	e.reserve(m);
	for (int i=0; i<m; ++i) e.emplace_back(A[i], B[i]);
	for (int i=0; i<n; ++i) {
		e.emplace_back(i, X);
		for (int j=0; j<10; ++j) if (1&(i>>j)) {
			e.emplace_back(i, bvo+j);
		}
	}
	for (int i=0; i<10; ++i) {
		e.emplace_back(bvo+i, X);
		e.emplace_back(bvo+i, Y);
	}

	//    -- 1 -- 2
	//   /
	//  0 -- 3 -- 4 -- 5
	//   \
	//    -- 6 -- 7 -- 8 -- 9

	e.emplace_back(bvo+0, bvo+1);
	e.emplace_back(bvo+1, bvo+2);

	e.emplace_back(bvo+0, bvo+3);
	e.emplace_back(bvo+3, bvo+4);
	e.emplace_back(bvo+4, bvo+5);

	e.emplace_back(bvo+0, bvo+6);
	e.emplace_back(bvo+6, bvo+7);
	e.emplace_back(bvo+7, bvo+8);
	e.emplace_back(bvo+8, bvo+9);

	InitG(Y+1, int(e.size()));
	for (int i=0; i<int(e.size()); ++i) {
		MakeG(i, e[i].first, e[i].second);
	}
}

}

void Alice(int n, int m, int A[], int B[]) { ALICE::Alice(n, m, A, B); }

Bob

#include <vector>
#include <map>
#include <utility>
using namespace std;
using pp=pair<int,int>;

void InitMap(int N, int M);
void MakeMap(int A, int B);

namespace BOB {
int deg[1500];
bool ee[1500][1500]; // edge exist?
vector<pp> oe;       // original edges
bool iso[1500];      // is original?
int om[1500];        // original number

vector<int> be[1500]; // bit edges
map<pp, int> fp;      // fingerprints: (depth, maxdepth)
int dfs(int x, int p, int d) {
	int mxd = d;
	for (int y:be[x]) if (y != p) {
		int tmp = dfs(y, x, d+1);
		if (mxd < tmp) mxd = tmp;
	}
	fp[{d, mxd}] = x;
	return mxd;
}

void Bob(int n, int m, int a[], int b[]) {
	for (int i=0; i<m; ++i) {
		++deg[a[i]]; ++deg[b[i]];

		ee[a[i]][b[i]] = ee[b[i]][a[i]] = true;
	}

	int X, Y;
	for (X=0; X<n; ++X) if (deg[X] == n-2) break;
	for (Y=0; Y<n; ++Y) if (X!=Y && !ee[X][Y]) break;

	static int bv[20], bvn = 0;
	for (int i=0; i<n; ++i) if (ee[i][Y]) bv[bvn++] = i;

	for (int i=0; i<bvn; ++i) { int ba = bv[i];
		for (int j=0; j<bvn; ++j) { int bb = bv[j];
			if (ee[ba][bb]) be[ba].push_back(bb);
		}
	}

	//    -- 1 -- 2
	//   /
	//  0 -- 3 -- 4 -- 5
	//   \
	//    -- 6 -- 7 -- 8 -- 9

	int rt; // root
	for(rt=0; rt<bvn; ++rt) if (be[bv[rt]].size() == 3lu) break;
	rt = bv[rt];
	dfs(rt, -1, 0);

	int bf[10]; // bits found
	pp bffp[10] = {
		{0, 4},
		{1, 2}, {2, 2},
		{1, 3}, {2, 3}, {3, 3},
		{1, 4}, {2, 4}, {3, 4}, {4, 4}
	}; // bit fingerprints
	for (int i=0; i<10; ++i) bf[i] = fp[bffp[i]];
	for (int i=0; i<n; ++i) if (i!=X && i!=Y && be[i].empty()) {
		iso[i] = true;
		for (int j=0; j<10; ++j) if (ee[i][bf[j]]) om[i] += (1<<j);
	}

	for (int i=0; i<n; ++i) if (iso[i]) {
		for (int j=0; j<i; ++j) if (iso[j] && ee[i][j]) {
			oe.emplace_back(om[i], om[j]);
		}
	}

	InitMap(n-12, int(oe.size()));
	for (auto [x, y]: oe) {
		MakeMap(x, y);
	}
}
}

void Bob(int V, int U, int C[], int D[]) { BOB::Bob(V, U, C, D); }

Compilation message (stderr)

Alice.cpp:33:2: warning: multi-line comment [-Wcomment]
   33 |  //   \
      |  ^

Bob.cpp:52:2: warning: multi-line comment [-Wcomment]
   52 |  //   \
      |  ^

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