Submission #945901

#	Time	Username	Problem	Language	Result	Execution time	Memory
945901		pcc	Airline Route Map (JOI18_airline)	C++17	100 / 100	1284 ms	83392 KiB

Alice

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


const int mxn = 1020;
const int H = 10;
/*
	InitG( 3, 2 );
	MakeG( 1, 2 );
*/
#define pii pair<int,int>
#define fs first
#define sc second

namespace ALICE{
	vector<pair<int,int>> edges;
	void GO(int N,int M,int A[],int B[]){
		for(int i = 0;i<M;i++){
			edges.push_back({A[i],B[i]});
		}
		for(int i = 0;i<H;i++){
			for(int j = 0;j<N;j++){
				if(j&(1<<i)){
					edges.push_back({j,N+i});
				}
			}
			if(i)edges.push_back({N+i-1,N+i});
			edges.push_back({N+i,N+H});
		}
		for(int i = 0;i<N+H;i++){
			edges.push_back({i,N+H+1});
		}
		InitG(N+H+2,edges.size());
		int pt = 0;
		//cerr<<"ALICE:"<<endl;
		for(auto &i:edges){
			//cerr<<i.fs<<' '<<i.sc<<endl;
		}
		//cerr<<endl;
		for(auto &i:edges)MakeG(pt++,i.fs,i.sc);
		return;
	}
}

void Alice( int N, int M, int A[], int B[] ){
	ALICE::GO(N,M,A,B);
}

Bob

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

#define pii pair<int,int>
#define fs first
#define sc second

/*
InitMap( 3, 2 );
MakeMap( 1, 2 );
*/

namespace BOB{
	const int H = 10;
	const int mxn = 1020;
	set<int> g[mxn];
	int N,n;
	bitset<mxn> bit;
	int dp[mxn];
	int N10,N11;
	void get_ind(){
		for(int i = 0;i<N;i++){
			if(g[i].size() == N-2){
				N11 = i;
				//cerr<<"N11:"<<i<<endl;
				for(int j = 0;j<N;j++){
					if(i==j||g[i].find(j) != g[i].end())continue;
					N10 = j;
					//cerr<<"N10:"<<j<<endl;
					return;
				}
			}
		}
		assert(false);
		return;
	}
	vector<int> bg[mxn];
	vector<int> get_num(){
		vector<int> vv;
		for(auto &i:g[N10]){
			bit[i] = true;
			vv.push_back(i);
		}
		for(auto &i:vv){
			for(auto &j:g[i]){
				if(bit[j]){
					bg[i].push_back(j);
				}
			}
		}
		vector<int> one;
		for(auto &i:vv){
			//cerr<<i<<":";for(auto &j:bg[i])cerr<<j<<' ';cerr<<endl;
			if(bg[i].size() == 1)one.push_back(i);
		}
		assert(one.size()==2);
		//cerr<<"ONE:"<<one[0]<<' '<<one[1]<<endl;
		int pre = -1,now = (g[one[0]].size()>g[one[1]].size()?one[0]:one[1]);
		vector<int> re;
		bool flag = true;
		while(flag){
			re.push_back(now);
			flag = false;
			for(auto nxt:bg[now]){
				if(!bit[nxt]||nxt == pre)continue;
				pre = now;
				now = nxt;
				flag = true;
				break;
			}
		}
		return re;
	}
	vector<pii> ans;

	void answer(){
		//cerr<<N<<":"<<ans.size()<<endl;
		for(auto &i:ans){
			//cerr<<i.fs<<' '<<i.sc<<endl;
		}
		InitMap(N-H-2,ans.size());
		for(auto &i:ans){
			//cerr<<i.fs<<' '<<i.sc<<endl;
			MakeMap(i.fs,i.sc);
		}
		return;
	}

	void GO(int NN,int M,int A[],int B[]){
		N = NN;
		n = N-12;
		for(int i = 0;i<M;i++){
			g[A[i]].insert(B[i]);
			g[B[i]].insert(A[i]);
		}
		//cerr<<"BOB"<<endl;
		for(int i = 0;i<M;i++){
			//cerr<<A[i]<<' '<<B[i]<<endl;
		}
		//cerr<<endl;
		get_ind();
		auto v = get_num();
		assert(v.size() == H);
		for(auto &i:v)bit[i] = true;
		bit[N10] = bit[N11] = true;
		for(int i = 0;i<H;i++){
			for(auto nxt:g[v[i]]){
				dp[nxt] |= 1<<i;
			}
		}
		for(int i = 0;i<N;i++){
			if(bit[i])continue;
			for(auto nxt:g[i]){
				if(nxt<i||bit[nxt])continue;
				ans.push_back({dp[i],dp[nxt]});
			}
		}
		answer();
	}
}

void Bob( int V, int U, int C[], int D[] ){
	BOB::GO(V,U,C,D);
}

Compilation message (stderr)

Alice.cpp: In function 'void ALICE::GO(int, int, int*, int*)':
Alice.cpp:39:13: warning: unused variable 'i' [-Wunused-variable]
   39 |   for(auto &i:edges){
      |             ^

Bob.cpp: In function 'void BOB::get_ind()':
Bob.cpp:26:19: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   26 |    if(g[i].size() == N-2){
      |       ~~~~~~~~~~~~^~~~~~
Bob.cpp: In function 'void BOB::answer()':
Bob.cpp:81:13: warning: unused variable 'i' [-Wunused-variable]
   81 |   for(auto &i:ans){
      |             ^

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