Submission #126182

#	Time	Username	Problem	Language	Result	Execution time	Memory
126182		tjd229	Airline Route Map (JOI18_airline)	C++14	100 / 100	1022 ms	25708 KiB

Alice

#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include <vector>
#define pii pair<int,int>
using namespace std;
void Alice( int N, int M, int A[], int B[] ){
	vector<pii > ex;
	int is = N + 10;
	int d1 = is + 1;
	for (int i = 0; i < N; ++i) {
		ex.push_back({ is,i });
		int ix = 1 + i;
		for (int k = 0; k < 10 && ix; ++k,ix>>=1) {
			if (ix & 1) ex.push_back({ N + k,i });
		}
	}
	for (int i = 1; i < 10; ++i) ex.push_back({N+i-1,N+i});
	ex.push_back({ is,d1 });
	InitG(N+12,M+ex.size());
	for (int i = 0; i < M; ++i) MakeG(i,A[i],B[i]);
	for (int i = 0; i < ex.size(); ++i) MakeG(M+i,ex[i].first,ex[i].second);
}

Bob

#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include <vector>
#include <deque>
#define pii pair<int,int>
using namespace std;
vector<int> edge[1012];
int ix[1012];
void Bob( int V, int U, int C[], int D[] ){
	int N = V - 12;
	int d1, is;
	vector<pii > ans;
	vector<int> info;
	deque<int> dq;
	for (int i = 0; i < U; ++i) {
		edge[C[i]].push_back(D[i]);
		edge[D[i]].push_back(C[i]);
	}
	for (int i = 0; i < V; ++i) {
		if (edge[i].size() == 1) {
			int candi = edge[i][0];
			if (edge[candi].size() == N + 1) {
				d1 = i;
				is = candi;
			}
		}
	}
	ix[is] = 1;
	for (auto dst : edge[is]) 
		ix[dst] = 1;
	
	
	for (int i = 0; i < V && dq.empty(); ++i) {
		if (ix[i] == 0) dq.push_back(i),ix[i]=-1;
	}
	
	//return;
	while (dq.size() < 10) {
		int i = dq.front();
		for (auto to : edge[i]) {
			if (ix[to] == 0) {
				dq.push_front(to);
				ix[to] = -1;//in q
				break;
			}
		}
		i = dq.back();
		for (auto to : edge[i]) {
			if (ix[to] == 0) {
				dq.push_back(to);
				ix[to] = -1;
				break;
			}
		}
	}
	while (dq.size()) info.push_back(dq.front()),dq.pop_front();


	if (edge[info.back()].size() == (N >> 1) + (N & 1)+1) {
		for (int i = 0; i < 5; ++i)
			info[i] ^= info[9 - i]^= info[i] ^= info[9 - i];
	}
	ix[is] = ix[d1] = -1;
	for (int i = 0; i < V; ++i) if(ix[i]>=0) ix[i] = 0;	
	for (int i = 0; i < info.size(); ++i) {
		for (auto to : edge[info[i]]) {
			if(ix[to]>=0)
				ix[to] += (1 << i);
		}
	}
	for (int i = 0; i < U; ++i) {
		if (ix[C[i]] > 0 && ix[D[i]] > 0) {
			ans.push_back({ix[C[i]]-1, ix[D[i]]-1});
		}
	}

	InitMap(N,ans.size());
	for (auto e : ans)
		MakeMap(e.first,e.second);
}

Compilation message (stderr)

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:22:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ex.size(); ++i) MakeG(M+i,ex[i].first,ex[i].second);
                  ~~^~~~~~~~~~~

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:23:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (edge[candi].size() == N + 1) {
        ~~~~~~~~~~~~~~~~~~~^~~~~~~~
Bob.cpp:60:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (edge[info.back()].size() == (N >> 1) + (N & 1)+1) {
      ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Bob.cpp:66:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < info.size(); ++i) {
                  ~~^~~~~~~~~~~~~
Bob.cpp:29:9: warning: 'is' may be used uninitialized in this function [-Wmaybe-uninitialized]
  ix[is] = 1;
  ~~~~~~~^~~
Bob.cpp:64:18: warning: 'd1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  ix[is] = ix[d1] = -1;
           ~~~~~~~^~~~

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