Submission #164064

#	Time	Username	Problem	Language	Result	Execution time	Memory
164064		oolimry	Airline Route Map (JOI18_airline)	C++14	37 / 100	2502 ms	72196 KiB

Alice

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

void Alice( int n, int m, int A[], int B[] ){
	int cnt = 0;
	vector<int> nums;
	for(int i = 0;i < 1024;i++){
		int bits = 0;
		for(int j = 1;j < 1024;j *= 2){
			if((i & j) != 0) bits++;
		}
		if(bits >= 2){
			nums.push_back(i);
		}
		if(nums.size() == n) break;
	}
	typedef pair<int,int> ii;
	vector<ii> edges;
	for(int i = 0;i < m;i++){
		edges.push_back(ii(A[i],B[i]));
	}
	
	int x = n+10;
	int y = n+11;
	int anchor[10];
	for(int i = 0;i < 10;i++) anchor[i] = n+i;
	
	edges.push_back(ii(x,y));
	for(int i = 0;i < 10;i++){
		edges.push_back(ii(y,anchor[i]));
	}
	
	for(int i = 1;i < 9;i++){
		edges.push_back(ii(anchor[0],anchor[i]));
		edges.push_back(ii(anchor[i],anchor[i+1]));
	}
	
	
	for(int i = 0;i < n;i++){
		int k = nums[i];
		for(int j = 0;j < 10;j++){
			if((k & (1 << j)) != 0){
				edges.push_back(ii(i,anchor[j]));
			}
		}
	}
	/*
	for(ii x : edges){
		cout << x.first << " " << x.second << "\n";
	}
	//*/
	InitG(n+12,edges.size());
	for(int i = 0;i < edges.size();i++){
		MakeG(i,edges[i].first,edges[i].second);
	}
	//cout << "\n\n";
}

Bob

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

void Bob( int n, int m, int C[], int D[] ){
    
	int on = n - 12;
	vector<int> nums;
	typedef pair<int,int> ii;
	set<ii> edges;
	for(int i = 0;i < 1024;i++){
		int bits = 0;
		for(int j = 1;j < 1024;j *= 2){
			if((i & j) != 0) bits++;
		}
		if(bits >= 2){
			nums.push_back(i);
		}
		if(nums.size() == on) break;
	}
	
	vector<int> adj[n];
	for(int i = 0;i < m;i++){
		adj[C[i]].push_back(D[i]);
		adj[D[i]].push_back(C[i]);
		//cout << C[i] << " " << D[i] << "\n";
		edges.insert(ii(C[i],D[i]));
		edges.insert(ii(D[i],C[i]));
	}
    if(n > 52) return;
	int x, y;
	for(int i = 0;i < n;i++){
		if(adj[i].size() == 1){
			x = i;
			y = adj[i][0];
			break;
		}
	}
	
	//cout << x << "\n" << y << "\n";
	
	vector<int> aa;
	for(int i = 0;i < n;i++){
		if(i == x || i == y){
			continue;
		}
		if(edges.find(ii(i,y)) != edges.end()){
			aa.push_back(i);
		}
	}
	set<int> anchorSet;
	for(int k : aa){
		//cout << k << " ";
		anchorSet.insert(k);
	}
	
	int anchor[10];
	
	fill(anchor,anchor+10,-1);
	for(int i = 0;i < 10;i++){
		int cnt = 0;
		for(int j = 0;j < 10;j++){
			if(edges.find(ii(aa[i],aa[j])) != edges.end()){
				cnt++;
			}
		}
		if(cnt == 8){
			anchor[0] = aa[i];
		}
		else if(cnt == 1){
			anchor[9] = aa[i];
		}
	}
	
	int cur = anchor[9];
	for(int i = 9;i >= 2;i--){
		for(int v : adj[cur]){
			if(v != anchor[0] && anchorSet.find(v) != anchorSet.end()){
				if(i == 9 || v != anchor[i+1]){
					cur = v;
					anchor[i-1] = cur;
					break;
				} 
			}
		}
	}
	bool extras[n];
	int anchorMap[n];
	int normalMap[n];
	fill(extras,extras+n,false);
	//unordered_map<int,int> anchorMap;
	//cout << "\n";
	for(int i =0 ;i < 10;i++){
		//cout << anchor[i] << " ";
		extras[anchor[i]] = true;
		anchorMap[anchor[i]] = i;
	}
	extras[x] = true;
	extras[y] = true;
	//cout << "\n";
	//unordered_map<int,int> normalMap;
	for(int u = 0;u < n;u++){
		int value = 0;
		if(extras[u]) continue;
		for(int v : adj[u]){
			if(!extras[v]) continue;
			
			int bit = anchorMap[v];
			value |= (1 << bit);
		}
		int pos = lower_bound(nums.begin(),nums.end(),value) - nums.begin();
		normalMap[u] = pos;
		//cout << u << " " << pos << "\n";
	}
	vector<ii> finalEdges;
	for(int i = 0;i < m;i++){
		int u = C[i];
		int v = D[i];
		if(extras[u] || extras[v]) continue;
		finalEdges.push_back(ii(normalMap[u],normalMap[v]));
	}
	
	//cout << "\n";
	//for(ii k : finalEdges) cout << k.first << " " << k.second << "\n";
	
	InitMap(on, finalEdges.size());
	for(ii k : finalEdges) MakeMap(k.first,k.second);
}

Compilation message (stderr)

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:16:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(nums.size() == n) break;
      ~~~~~~~~~~~~^~~~
Alice.cpp:54:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i < edges.size();i++){
                ~~^~~~~~~~~~~~~~
Alice.cpp:6:6: warning: unused variable 'cnt' [-Wunused-variable]
  int cnt = 0;
      ^~~

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:19:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(nums.size() == on) break;
      ~~~~~~~~~~~~^~~~~
Bob.cpp:99:12: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
  extras[y] = true;
  ~~~~~~~~~~^~~~~~
Bob.cpp:98:12: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
  extras[x] = true;
  ~~~~~~~~~~^~~~~~

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