Submission #1220290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220290		salmon	Airline Route Map (JOI18_airline)	C++20	100 / 100	255 ms	23168 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>> edge;
	int lst[1100];
	int pow[11];
	vector<int> de;
	
	int it = 0;
	
	for(int i = 0; i < 10; i++){
		pow[i] = N + 50 + i;
		de.push_back(pow[i]);
	}

	for(int i = 0; i < N; i++){
		int cont = 0;
		
		while(cont < 2){
			it++;
			int c = it;
			
			cont = 0;
			
			while(c != 0){
				cont++;
				c -= (c&(-c));
			}
		}
		
		lst[i] = it;
		de.push_back(it);
		
		for(int i = 0; i < 10; i++){
			if( (it&(1<<i)) > 0 ){
				edge.push_back({it,pow[i]});
			}
		}
	}

	for(int i = 0; i < M; i++){
		edge.push_back({lst[A[i]],lst[B[i]]});
	}
	
	for(int i = 0; i < 9; i++){
		edge.push_back({pow[i],pow[i + 1]});
	}
	
	int b = N + 70;
	
	de.push_back(b);
	
	for(int i = 0; i < 10; i++) edge.push_back({pow[i],b});
	
	de.push_back(N + 100);
	
	edge.push_back({N + 100, b});
	
	InitG(de.size(), edge.size());
		
	sort(de.begin(),de.end());
	
	int i = 0;
	
	for(pair<int,int> ii : edge){
		int a = lower_bound(de.begin(),de.end(),ii.first) - de.begin();
		int b = lower_bound(de.begin(),de.end(),ii.second) - de.begin();
		MakeG(i,a,b);
		i++;
	}

	return;
}

Bob

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

void Bob( int V, int U, int C[], int D[] ){
	
	int d[V];
	
	vector<int> adjlst[V + 2];
	bool isten[V + 2];
	int itentity[V + 2];
	
	for(int i = 0; i < V; i++) d[i] = 0;
	for(int i = 0; i < V; i++) isten[i] = false;
	
	for(int i = 0; i < U; i++){
		d[C[i]]++;
		d[D[i]]++;
		
		adjlst[C[i]].push_back(D[i]);
		adjlst[D[i]].push_back(C[i]);
	}
	
	int mark = 0;
	int mark1 = 0;
	
	for(int i = 0; i < V; i++){
		if(d[i] == 1){
			mark = i;
		}
	}
	
	mark1 = adjlst[mark][0];

	vector<int> ten;
	vector<int> endp;
	
	for(int i : adjlst[mark1]){
		if(i == mark) continue;
		isten[i] = true;
		ten.push_back(i);
	}

	for(int i : ten){
		int cont = 0;
		for(int j : adjlst[i]){
			if(isten[j]) cont++;
		}
		if(cont == 1) endp.push_back(i);
	}
	
	ten.clear();
	
	if(d[endp[0]] < d[endp[1]]) swap(endp[0],endp[1]);
	
	endp.pop_back();
		
	int i = endp[0];
	int p = -1;
	
	while(true){
		ten.push_back(i);
		bool die = true;
		
		for(int j : adjlst[i]){
			if(!isten[j] || j == p) continue;
			p = i;
			i = j;
			die = false;
			break;
		}
		
		if(die) break;
	}

	assert(ten.size() == 10);
	
	for(int i = 0; i < V; i++) itentity[i] = -1;
	
	itentity[mark] = -2;
	itentity[mark1] = -2;
	
	for(int i = 0; i < 10; i++){
		itentity[ten[i]] = V + 100 + i;
	}
	
	vector<int> de;
	
	for(int i = 0; i < V; i++){
		if(itentity[i] == -1){
			itentity[i] = 0;
			
			for(int j : adjlst[i]){
				if(itentity[j] >= V + 100){
					itentity[i] += (1<<(itentity[j]-V-100)) ;
				}
			}
			
			de.push_back(itentity[i]);
		}
	}
	
	sort(de.begin(),de.end());
	
	vector<pair<int,int>> edge;
	
	for(int i = 0; i < U; i++){
		if(itentity[C[i]] < 0 || itentity[D[i]] < 0) continue;
		if(itentity[C[i]] >= V + 100 || itentity[D[i]] >= V + 100) continue;
		
		int a = lower_bound(de.begin(),de.end(),itentity[C[i]]) - de.begin(); 
		int b = lower_bound(de.begin(),de.end(),itentity[D[i]]) - de.begin();
		
		edge.push_back({a,b});
	}
	
	InitMap( V - 12, edge.size());
	
	
	for(pair<int,int> ii : edge) MakeMap(ii.first,ii.second);
	
	
}

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