Submission #1221443

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221443		emptypringlescan	Airline Route Map (JOI18_airline)	C++17	100 / 100	166 ms	23156 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> > ed;
	for(int i=0; i<m; i++){
		ed.push_back({A[i],B[i]});
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<10; j++){
			if(i&(1<<j)){
				ed.push_back({i,n+j});
			}
		}
	}
	for(int i=n; i<n+9; i++) ed.push_back({i,i+1});
	for(int i=0; i<n+10; i++) ed.push_back({i,n+10});
	for(int i=n; i<n+10; i++) ed.push_back({i,n+11});
	InitG(n+12,(int)ed.size());
	for(int i=0; i<(int)ed.size(); i++){
		//cout << ed[i].first << ' ' << ed[i].second << '\n';
		MakeG(i,ed[i].first,ed[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;
	if(n==1){
		InitMap(1,0);
		return;
	}
	int deg[v];
	memset(deg,0,sizeof(deg));
	vector<int> adj[v];
	for(int i=0; i<u; i++){
		deg[C[i]]++;
		deg[D[i]]++;
		adj[C[i]].push_back(D[i]);
		adj[D[i]].push_back(C[i]);
	}
	pair<int,int> mx={-1,-1};
	for(int i=0; i<v; i++){
		mx=max(mx,{deg[i],i});
	}
	assert(mx.first==n+10);
	int is[v];
	memset(is,0,sizeof(is));
	is[mx.second]=1;
	int hm=mx.second;
	for(int i:adj[mx.second]) is[i]=1;
	int bn=-1;
	for(int i=0; i<v; i++) if(!is[i]) bn=i;
	assert(deg[bn]==10);
	int isb[v];
	memset(isb,0,sizeof(isb));
	mx={1e9,-1};
	for(int i:adj[bn]){
		isb[i]=1;
		mx=min(mx,{deg[i],i});
	}
	vector<int> bts;
	int cur=mx.second;
	for(int i=0; i<10; i++){
		bts.push_back(cur);
		isb[cur]=0;
		for(int j:adj[cur]){
			if(isb[j]){
				cur=j;
				break;
			}
		}
	}
	assert((int)bts.size()==10);
	reverse(bts.begin(),bts.end());
	for(int i=0; i<v; i++) isb[i]=-1;
	int cnt=0;
	for(int i:bts){
		is[i]=0,isb[i]=cnt;
		cnt++;
	}
	is[hm]=0;
	int ind[v];
	memset(ind,-1,sizeof(ind));
	cnt=0;
	for(int i=0; i<v; i++){
		if(!is[i]) continue;
		cnt++;
		ind[i]=0;
		for(int j:adj[i]){
			if(isb[j]==-1) continue;
			ind[i]^=(1<<isb[j]);
		}
	}
	assert(cnt==n);
	vector<pair<int,int> > ed;
	for(int i=0; i<u; i++){
		if(is[C[i]]&&is[D[i]]){
			ed.push_back({ind[C[i]],ind[D[i]]});
		}
	}
	InitMap(n,(int)ed.size());
	for(auto i:ed) MakeMap(i.first,i.second);
}

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