Submission #209539

#	Time	Username	Problem	Language	Result	Execution time	Memory
209539		coldEr66	Airline Route Map (JOI18_airline)	C++14	100 / 100	672 ms	22824 KiB

Alice

#include "Alicelib.h"
#include <cassert>
#include <cstdio>
using namespace std;
#define REP1(i,n) for(int i=1;i<=n;i++)
#define REP(i,n) for(int i=0;i<n;i++)

void Alice( int N, int M, int A[], int B[] ){
	int V = N + 12; // N~N+9 ,N+10~N+11;
	int U = M;
	REP (i,N) {
		U += __builtin_popcount(i);
	}
	U += 9, U += 2*N;
	InitG(V,U);
	int idx = 0;
	REP (i,M) {
		MakeG(idx++,A[i],B[i]);
	}
	for (int i=N;i<N+9;i++) MakeG(idx++,i,i+1);
	REP (i,N) {
		MakeG(idx++,i,N+10), MakeG(idx++,i,N+11);
		int tmp = i;
		int bit = 0;
		while (tmp) {
			if (tmp&1) MakeG(idx++,i,N+bit);
			tmp >>= 1;
			bit++;
		}
	}
}

Bob

#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
#define REP1(i,n) for(int i=1;i<=n;i++)
#define REP(i,n) for(int i=0;i<n;i++)
#define SZ(a) (int)a.size()

const int MAXn=1e3+20;

bitset<MAXn> bs[MAXn];
int bit[MAXn];
int deg[MAXn];
int id[MAXn];
vector<int> e[MAXn];
int p[MAXn];
void dfs(int x,int par,int b){
	// cout << "dfs " << x << endl;
	bit[x] = (1<<b);
	for (auto i:e[x]) {
		if (i == par || id[i] != 2) continue;
		dfs(i,x,b+1);
	}
}
void Bob( int V, int U, int C[], int D[] ){
	int N = V-12;
	REP (i,U) {
		bs[C[i]][D[i]] = 1;
		bs[D[i]][C[i]] = 1;
		e[C[i]].emplace_back(D[i]);
		e[D[i]].emplace_back(C[i]);
	}
	// REP (i,U) {
	// 	cout << i << ": ";
	// 	for (auto it:e[i]) {
	// 		cout << it << ' ';
	// 	}
	// 	cout << endl;
	// }
	int S = -1, T = -1;
	REP (i,V) {
		if (int(bs[i].count()) != N) continue;
		for (int j=i+1;j<V;j++) {
			if (int(bs[j].count()) != N) continue;
			if (int((bs[i] & bs[j]).count()) == N) {
				S = i, T = j;
				id[S] = 1, id[T] = 1;
			}
		}
	}
	// cout << S << ' ' << T << endl;
	vector<int> tmp;
	REP (i,V) {
		if (bs[S][i] == 0 && i != S && i != T) {
			tmp.emplace_back(i);
			id[i] = 2;
		}
	}
	int X = -1;
	REP (i,SZ(tmp)) {
		int cur = tmp[i];
		int cnt = 0;
		for (auto it:e[cur]) {
			if (id[it] == 2) cnt++;
		}
		// cout << "cnt " << cnt << endl;
		if (cnt == 1) {
			// cout << "HI" << endl;
			if (X == -1) X = cur;
			else if (SZ(e[cur]) > SZ(e[X])) X = cur;
		}
	}
	dfs(X,X,0);
	// REP (i,V) cout << i << ' ' << bit[i] << endl;
	int M = 0;
	REP (i,V) {
		if (id[i] == 0) {
			for (auto it:e[i]) {
				if (id[it] == 0) M++;
				if (id[it] == 2) {
					p[i] += bit[it];
				}
			}
		}
	}
	// REP (i,V) cout << "p: " << p[i] << endl;
	// REP (i,V) cout << "id: " << id[i] << endl;
	M /= 2;
	InitMap(N,M);
	REP (i,U) {
		if (id[C[i]] == 0 && id[D[i]] == 0) {
			MakeMap(p[C[i]],p[D[i]]);
		}
	}
}

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