Submission #1189254

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189254		12345678	Airline Route Map (JOI18_airline)	C++20	100 / 100	178 ms	25988 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>> edg;
	for (int i=0; i<M; i++) edg.push_back({A[i], B[i]});
	for (int i=0; i<10; i++)
	{
		for (int j=0; j<N; j++) if (j&(1<<i)) edg.push_back({N+i, j});
		if (i!=9) edg.push_back({N+i, N+i+1});
	}
	for (int i=0; i<N; i++) edg.push_back({N+10, i});
	edg.push_back({N+10, N+11});
	InitG(N+12, edg.size());
	int cnt=0;
	for (auto [u, v]:edg) MakeG(cnt++, u, v);
}

Bob

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

using namespace std;

const int nx=1020;

int adj[nx][nx], sp, bit[nx], cur=-1, code[nx], vs[nx];
vector<int> d[nx];

void Bob( int V, int U, int C[], int D[]){
	//cout<<"debug "<<U<<' '<<V<<'\n';
	for (int i=0; i<U; i++) adj[C[i]][D[i]]=adj[D[i]][C[i]]=1, d[D[i]].push_back(C[i]), d[C[i]].push_back(D[i]);
	for (int i=0; i<V; i++) if (d[i].size()==1&&d[d[i][0]].size()==V-11) sp=d[i][0], bit[i]=bit[sp]=vs[i]=vs[sp]=1;
	//cout<<"sp "<<sp<<'\n';
	cur=sp;
	for (int i=0; i<V; i++)
	{
		if (i!=sp&&!adj[sp][i])
		{
			//cout<<"here "<<i<<'\n';
			bit[i]=1;
			if (d[i].size()<d[cur].size()) cur=i;
		}
	}
	vs[cur]=1;
	for (int i=9; i>=0; i--)
	{
		//cout<<"c "<<cur<<' '<<d[cur].size()<<'\n';
		for (auto v:d[cur]) code[v]|=(1<<i);
		for (auto v:d[cur]) 
		{
			//cout<<"v "<<v<<' '<<vs[v]<<'\n';
			if (bit[v]&&!vs[v]) vs[v]=1, cur=v; 
		}
	}
	vector<pair<int, int>> edg;
	for (int i=0; i<U; i++) if (!bit[C[i]]&&!bit[D[i]]) edg.push_back({code[C[i]], code[D[i]]});
	//cout<<V-12<<' '<<edg.size()<<'\n';
	InitMap(V-12, edg.size());
	for (auto [u, v]:edg) MakeMap(u, v);  
}

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