Submission #1283047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283047		julia_08	Airline Route Map (JOI18_airline)	C++20	100 / 100	199 ms	30316 KiB

Alice

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

using namespace std;

const int MAXN = 1e3 + 20;

static vector<int> adj[MAXN];

void add(int a, int b){
	adj[a].push_back(b);
	adj[b].push_back(a);
}

void Alice(int n, int m, int a[], int b[]){

	for(int i=0; i<m; i++) add(a[i], b[i]);

	for(int i=0; i<n; i++){

		for(int j=0; j<10; j++){
			if(i & (1 << j)){
				add(i, n + j);
			}
		}

		add(i, n + 10);

	}

	for(int i=0; i<10; i++){

		add(n + i, n + 10);
		add(n + i, n + 11);		
		
		if(i < 9) add(n + i, n + i + 1);

	}

	int v = n + 12;

	int u = 0;

	for(int i=0; i<v; i++) u += (int) adj[i].size();

	u /= 2;

	InitG(v, u);	

	int cnt = 0;

	for(int i=0; i<v; i++){
		for(auto j : adj[i]){
			if(i < j) MakeG(cnt++, i, j);
		}
	}

}

Bob

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

using namespace std;

const int MAXN = 1e3 + 20;

int marc[MAXN], id[MAXN];

static vector<int> adj[MAXN];

void Bob(int v, int u, int c[], int d[]){
	
	for(int i=0; i<u; i++){
		adj[c[i]].push_back(d[i]);
		adj[d[i]].push_back(c[i]);
	}

	int x = 0;

	for(int i=0; i<v; i++) if(adj[i].size() > adj[x].size()) x = i;

	marc[x] = 1;

	for(auto i : adj[x]) marc[i] ++;

	int y = 0;

	for(int i=0; i<v; i++){
		if(!marc[i]) y = i;
		marc[i] = 0;
	}

	for(auto i : adj[y]) marc[i] = 1;
	 	
	int first_bit = -1;

	for(auto i : adj[y]){

		int cnt = 0;

		for(auto j : adj[i]) cnt += marc[j];

		if(cnt == 1){
			if(first_bit == -1 || (int) adj[i].size() > (int) adj[first_bit].size()){
				first_bit = i; 
			}
		}

	}

	vector<int> ord;

	int cur = first_bit;

	while((int) ord.size() < 10){
		
		ord.push_back(cur);
		marc[cur] = 0;
		id[cur] = 1e9;

		for(auto i : adj[cur]) if(marc[i]) cur = i;

	}

	for(int i=0; i<10; i++) for(auto j : adj[ord[i]]) id[j] += (1 << i);
	
	int n = v - 12;
	
	vector<pair<int, int>> edges;

	for(int i=0; i<v; i++){
				
		if(id[i] >= n) continue;

		for(auto j : adj[i]){
			if(id[j] < id[i]){
				edges.push_back({id[j], id[i]});
			}
		}

	}

	InitMap(n, (int) edges.size());

	for(auto [a, b] : edges) MakeMap(a, b);

}

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