Submission #100682

#	Time	Username	Problem	Language	Result	Execution time	Memory
100682		JPN20	Airline Route Map (JOI18_airline)	C++17	100 / 100	862 ms	31264 KiB

Alice

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

vector<pair<int, int>> vec;

void Alice(int N, int M, int A[], int B[] ){
	// 上界の辺
	vec.push_back(make_pair(0, 1));
	for (int i = 2; i < 12; i++) vec.push_back(make_pair(1, i));
	vec.push_back(make_pair(2, 5));
	for (int i = 3; i < 11; i++) vec.push_back(make_pair(i, i + 1));
	
	// 上界と下界をつなげる辺
	vector<int>ss;
	for (int i = 0; i < 1024; i++) {
		int cnts = 0;
		for (int j = 0; j < 10; j++) { if ((i / (1 << j)) % 2 == 1) cnts++; }
		if (cnts >= 2) ss.push_back(i);
	}
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < 10; j++) {
			if ((ss[i] / (1 << j)) % 2 == 1) vec.push_back(make_pair(i + 12, j + 2));
		}
	}
	
	// 下界の辺
	for (int i = 0; i < M; i++) vec.push_back(make_pair(A[i] + 12, B[i] + 12));
	
	// 関数の呼び出し
	InitG(N + 12, vec.size());
	for (int i = 0; i < vec.size(); i++) MakeG(i, vec[i].first, vec[i].second);
	return;
}

Bob

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

vector<int> X[1019], G[1019]; int dist[1019], num[1019], rev[1019], L[1024];

void Bob( int V, int U, int C[], int D[] ){
	// 状態を求める
	for (int i = 0; i < U; i++) {
		X[C[i]].push_back(D[i]);
		X[D[i]].push_back(C[i]);
	}
	
	// 神の頂点を求める
	int God = -1;
	for (int i = 0; i < V; i++) {
		if (X[i].size() == 1) God = i;
	}
	
	// 神からの距離を求める
	for (int i = 0; i < V; i++) dist[i] = 10000;
	queue<int>Q; Q.push(God); dist[God] = 0;
	
	while (!Q.empty()) {
		int pos = Q.front(); Q.pop();
		for (int i = 0; i < X[pos].size(); i++) {
			if (dist[X[pos][i]] > dist[pos] + 1) {
				dist[X[pos][i]] = dist[pos] + 1;
				Q.push(X[pos][i]);
			}
		}
	}
	
	// 神から 2 の頂点の番号を求める
	int cnts = 0;
	for (int i = 0; i < V; i++) num[i] = -1;
	for (int i = 0; i < U; i++) {
		if (dist[C[i]] == 2 && dist[D[i]] == 2) {
			G[C[i]].push_back(D[i]);
			G[D[i]].push_back(C[i]);
		}
		if (dist[C[i]] == 3 && dist[D[i]] == 3) cnts++;
	}
	int root = -1, subroot = -1;
	for (int i = 0; i < V; i++) {
		int chil = G[i][0];
		if (G[i].size() == 1 && G[chil].size() == 3) { root = i; num[i] = 0; }
		if (G[i].size() == 1 && (G[G[chil][0]].size() == 3 || G[G[chil][1]].size() == 3)) { subroot = i; num[i] = 1; }
	}
	
	int cntv = 2;
	while (true) {
		for (int i = 0; i < G[subroot].size(); i++) {
			if (num[G[subroot][i]] == -1) {
				num[G[subroot][i]] = cntv;
				subroot = G[subroot][i];
				cntv++;
				break;
			}
		}
		if (cntv == 10) break;
	}
	
	// 普通の頂点の割当を求める
	for (int i = 0; i < U; i++) {
		if (dist[C[i]] == 3 && dist[D[i]] == 2) swap(C[i], D[i]);
		if (dist[C[i]] == 2 && dist[D[i]] == 3) {
			rev[D[i]] += (1 << num[C[i]]);
		}
	}
	
	vector<int>ss;
	for (int i = 0; i < 1024; i++) {
		int cnts = 0;
		for (int j = 0; j < 10; j++) { if ((i / (1 << j)) % 2 == 1) cnts++; }
		if (cnts >= 2) ss.push_back(i);
	}
	for (int i = 0; i < ss.size(); i++) L[ss[i]] = i;
	
	// 最終的に出力する
	InitMap(V - 12, cnts);
	for (int i = 0; i < U; i++) {
		if (dist[C[i]] == 3 && dist[D[i]] == 3) {
			MakeMap(L[rev[C[i]]], L[rev[D[i]]]);
		}
	}
	
	return;
}

Compilation message (stderr)

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

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:26:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < X[pos].size(); i++) {
                   ~~^~~~~~~~~~~~~~~
Bob.cpp:53:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < G[subroot].size(); i++) {
                   ~~^~~~~~~~~~~~~~~~~~~
Bob.cpp:78:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ss.size(); i++) L[ss[i]] = i;
                  ~~^~~~~~~~~~~
Bob.cpp:44:6: warning: variable 'root' set but not used [-Wunused-but-set-variable]
  int root = -1, subroot = -1;
      ^~~~

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