Submission #1199577

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199577		byunjaewoo	Airline Route Map (JOI18_airline)	C++20	100 / 100	182 ms	23236 KiB

Alice

#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;

void Alice( int N, int M, int A[], int B[] ){
	vector<pair<int, int>> vec;
	for(int i=0; i<M; i++) vec.emplace_back(A[i], B[i]);
	for(int i=0; i<N; i++) for(int j=0; j<10; j++) if(i&(1<<j)) vec.emplace_back(i, N+j);
	for(int i=0; i<9; i++) vec.emplace_back(N+i, N+i+1);
	for(int i=0; i<N; i++) vec.emplace_back(i, N+10), vec.emplace_back(i, N+11);
	InitG(N+12, vec.size());
	for(int i=0; i<vec.size(); i++) MakeG(i, vec[i].first, vec[i].second);
}

Bob

#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;

void Bob( int V, int U, int C[], int D[] ){
	int N=V-12;
	vector<pair<int, int>> vec;
	vector<vector<int>> adj(V);
	vector<bitset<1012>> bt(V);
	for(int i=0; i<U; i++) {
		adj[C[i]].push_back(D[i]), adj[D[i]].push_back(C[i]);
		bt[C[i]][D[i]]=true, bt[D[i]][C[i]]=true;
	}
	int v1=-1, v2=-1;
	for(int i=0; i<V; i++) for(int j=i+1; j<V; j++) {
		if(bt[i].count()==N && bt[j].count()==N && bt[i]==bt[j]) v1=i, v2=j;
	}
	vector<int> vd, vn, num;
	for(int i=0; i<V; i++) {
		if(bt[v1][i]) vn.push_back(i), num.push_back(0);
		else if(i!=v1 && i!=v2) vd.push_back(i);
	}
	for(int i=0; i<vd.size(); i++) {
		int cnt=0;
		for(int j:vd) cnt+=bt[vd[i]][j];
		if(cnt==1) {
			swap(vd[i], vd[0]); break;
		}
	}
	for(int i=1; i<vd.size(); i++) {
		for(int j=i; j<vd.size(); j++) if(bt[vd[i-1]][vd[j]]) {
			swap(vd[i], vd[j]); break;
		}
	}
	if(adj[vd[0]].size()<adj[vd.back()].size()) reverse(vd.begin(), vd.end());
	for(int i=0; i<vn.size(); i++) {
		for(int j=0; j<vd.size(); j++) if(bt[vn[i]][vd[j]]) num[i]+=(1<<j);
		for(int j=0; j<i; j++) if(bt[vn[i]][vn[j]]) vec.push_back({num[i], num[j]});
	}
	// for(auto [u, v]:vec) cout<<u<<", "<<v<<"\n";
	InitMap(N, vec.size());
	for(auto [u, v]:vec) MakeMap(u, v);
}

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