Submission #1219234

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219234		mertbbm	Airline Route Map (JOI18_airline)	C++20	37 / 100	166 ms	19292 KiB

Alice

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

//#define int long long 
//#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;

//InitG(v,u)
//MakeG(0,a,b)

//Alice
void Alice(int n, int m, int a[], int b[]){
	vector<pii>edge;
	for(int x=0;x<m;x++){
		edge.push_back({a[x],b[x]});
	}
	
	int ptr=n;
	vector<int>line;
	line.push_back(ptr);
	ptr++;
	for(int x=0;x<9;x++){
		edge.push_back({ptr,ptr-1});
		line.push_back(ptr);
		ptr++;
	}
	
	for(int x=0;x<n;x++){
		for(int y=0;y<10;y++){
			if(x&(1<<y)){
				edge.push_back({line[y],x});
			}
		}
	}
	
	for(int x=0;x<n+10;x++){
		edge.push_back({n+10,x});
		if(x<n) edge.push_back({n+11,x});
	}
	
	InitG(n+12,edge.size());
	int cur=0;
	for(auto it:edge){
		MakeG(cur,it.first,it.second);
		cur++;
	}
}

Bob

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

//#define int long long 
//#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;

//InitMap(N,M)
//MakeMap(a,b)

//Bob
void Bob(int v, int u, int c[], int d[]){
	pii rt={-1,-1};
	vector<int>adj[2005];
	
	for(int x=0;x<u;x++){
		adj[c[x]].push_back(d[x]);
		adj[d[x]].push_back(c[x]);
	}
	
	for(int x=0;x<v;x++){
		rt=max(rt,{adj[x].size(),x});
	}
	
	int done[2005];
	memset(done,0,sizeof(done));
	
	for(auto it:adj[rt.second]) done[it]=true;
	done[rt.second]=true;
	
	int take;
	for(int x=0;x<v;x++){
		if(!done[x]) take=x;
	}
	
	memset(done,0,sizeof(done));
	for(auto it:adj[take]) done[it]=true;
	done[rt.second]=true;
	done[take]=true;
	
	vector<int>adj2[2005];
	for(int x=0;x<u;x++){
		if(!done[c[x]]&&!done[d[x]]){
			adj2[c[x]].push_back(d[x]);
			adj2[d[x]].push_back(c[x]);
		}
	}
	
	vector<int>line;
	bool bit[v+5];
	memset(bit,0,sizeof(bit));
	
	for(int x=0;x<v;x++){
		if(adj2[x].size()==1&&!done[x]){
			int cur=x;
			while(1){
				done[cur]=true;
				line.push_back(cur);
				bit[cur]=true;
				bool nxt=false;
				for(auto it:adj2[cur]){
					if(done[it]) continue;
					nxt=true;
					cur=it;
				}
				if(!nxt) break;
			}
		}
	}
	
	if(adj[line[0]].size()<adj[line[9]].size()) reverse(line.begin(),line.end());
	
	int arr[v+5];
	memset(arr,0,sizeof(arr));
	for(int x=0;x<10;x++){
		for(auto it:adj[line[x]]){
			if(bit[it]) continue;
			arr[it]+=(1<<x);
		}
	}
	
	vector<pii>edge;
	for(int x=0;x<u;x++){
		int temp=d[x];
		int temp2=c[x];
		if(temp==rt.second||temp==take||temp2==rt.second||temp2==take) continue;
		if(bit[temp]||bit[temp2]) continue;
		edge.push_back({arr[temp],arr[temp2]});
	}
	
	InitMap(rt.first-10,edge.size());
	
	for(auto it:edge){
		MakeMap(it.first,it.second);
	}
}

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