Submission #1194255

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194255		yellowtoad	Airline Route Map (JOI18_airline)	C++20	100 / 100	172 ms	23232 KiB

Alice

#include "Alicelib.h"
#include <iostream>
#include <cassert>
#include <cstdio>
#include <vector>
#define f first
#define s second
using namespace std;

void Alice( int n, int m, int A[], int B[] ) {
	vector<pair<int,int>> edge;
	for (int i = 0; i < m; i++) edge.push_back({A[i],B[i]});
	for (int i = n; i < n+10; i++) for (int j = 0; j < n; j++) if ((j&(1<<(i-n))) > 0) edge.push_back({i,j});
	for (int i = n; i < n+10; i++) edge.push_back({n+10,i});
	for (int i = 0; i < n+10; i++) edge.push_back({n+11,i});
	edge.push_back({n,n+1});
	edge.push_back({n,n+2});
	edge.push_back({n+2,n+3});
	edge.push_back({n,n+4});
	for (int i = n+4; i < n+9; i++) edge.push_back({i,i+1});
	InitG(n+12,edge.size());
	for (int i = 0; i < edge.size(); i++) MakeG(i,edge[i].f,edge[i].s);
}

Bob

#include "Boblib.h"
#include <iostream>
#include <cassert>
#include <cstdio>
#include <vector>
#define f first
#define s second
using namespace std;

vector<int> edge[1020];
vector<pair<int,int>> ans;
int p[1020], d[1020];

void dfs(int u, int v) {
	for (int i = 0; i < edge[u].size(); i++) if ((edge[u][i] != v) && (p[edge[u][i]] == -1)) dfs(edge[u][i],u), d[u] = d[edge[u][i]]+1;
}

void dfs2(int u, int cnt) {
	p[u] = cnt;
	for (int i = 0; i < edge[u].size(); i++) if (p[edge[u][i]] == -1) dfs2(edge[u][i],cnt+1);
}

void Bob( int n, int m, int C[], int D[] ) {
	pair<int,int> maxx;
	for (int i = 0; i < m; i++) edge[C[i]].push_back(D[i]), edge[D[i]].push_back(C[i]);
	for (int i = 0; i < n; i++) {
		if (edge[i].size() == n-2) {
			p[i] = n-1;
			for (int j = 0; j < n; j++) if (j != i) p[j] = n-2;
			for (int j = 0; j < edge[i].size(); j++) p[edge[i][j]] = 0;
			break;
		}
	}
	for (int i = 0; i < n; i++) {
		if (p[i] == n-2) {
			for (int j = 0; j < edge[i].size(); j++) p[edge[i][j]] = -1;
			for (int j = 0; j < n; j++) {
				if (p[j] == -1) {
					int cnt = 0;
					for (int k = 0; k < edge[j].size(); k++) if (p[edge[j][k]] == -1) cnt++;
					maxx = max(maxx,{cnt,j});
				}
			}
			p[maxx.s] = n-12;
			dfs(maxx.s,-1);
			for (int j = 0; j < edge[maxx.s].size(); j++) {
				int u = edge[maxx.s][j];
				if (p[u] == -1) {
					if (d[u] == 0) {
						p[u] = n-11;
					} else if (d[u] == 1) {
						dfs2(u,n-10);
					} else {
						dfs2(u,n-8);
					}
				}
			}
			break;
		}
	}
	for (int i = 0; i < n; i++) {
		if ((n-12 <= p[i]) && (p[i] < n-2)) {
			for (int j = 0; j < edge[i].size(); j++) {
				if (n-12 <= p[edge[i][j]]) continue;
				p[edge[i][j]] += (1<<(p[i]-(n-12)));
			}
		}
	}
	for (int i = 0; i < m; i++) if ((p[C[i]] < n-12) && (p[D[i]] < n-12)) ans.push_back({p[C[i]],p[D[i]]});
	InitMap(n-12,ans.size());
	for (int i = 0; i < ans.size(); i++) MakeMap(ans[i].f,ans[i].s);
}

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