Submission #372309

#	Time	Username	Problem	Language	Result	Execution time	Memory
372309		hoaphat1	Airline Route Map (JOI18_airline)	C++17	0 / 100	801 ms	29740 KiB

Alice

#include<bits/stdc++.h>
 
using namespace std;
 
#include "Alicelib.h"
#include "Boblib.h"
 
void Alice( int N, int M, int A[], int B[] ) {
	if (N <= 2) {
		InitG(N, M);
		for (int i = 0; i < M; i++) MakeG(i, A[i], B[i]);
		return ;
	}
	vector<pair<int,int>> edges;
	for (int i = 0; i < M; i++) edges.emplace_back(A[i], B[i]);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < 10; j++) if ((i + 1) >> j & 1) edges.emplace_back(N + j, i);
	}
	for (int i = 0; i < N; i++) {
		edges.emplace_back(N + 11, i);
		edges.emplace_back(N + 10, i);
	}
	for (int i = 1; i < 10; i++) edges.emplace_back(N + i - 1, N + i);
	for (int i = 1; i < 12; i++) if (i != 10) edges.emplace_back(N + i, N + 10);
	InitG(N + 12, (int) edges.size());
	for (int i = 0; i < (int) edges.size(); i++) MakeG(i, edges[i].first, edges[i].second);
}

Bob

#include<bits/stdc++.h>
 
using namespace std;
 
#include "Alicelib.h"
#include "Boblib.h"
 
void Bob( int V, int U, int C[], int D[] ) {
	if (V <= 2) {
		InitMap(V, U);
		for (int i = 0; i < U; i++) MakeMap( C[i], D[i]);
		return ;
	}
	vector<pair<int,int>> edges;
	vector<int> cnt(V);
	vector<vector<int>> g(V);
	for (int i = 0; i < U; i++) {
		++cnt[C[i]]; ++cnt[D[i]];
		g[C[i]].push_back(D[i]);
		g[D[i]].push_back(C[i]);
	}
	int pos;
	for (int i = 0; i < V; i++) if (cnt[i] == V - 11) {
		pos = i;
		break;
	}
	vector<bool> old(V);
	for (auto& u : g[pos]) {
		old[u] = true;
	}
	vector<int> bit(10, -1);
	int last = max_element(cnt.begin(), cnt.end()) - cnt.begin();
	vector<bool> kt(V);
	for (auto& to : g[last]) kt[to] = true;
	kt[last] = true;
	for (int i = 0; i < V; i++) if (!kt[i]) {
		bit[0] = i;
		break;
	}
	last = bit[0];
	for (int i = 1; i < 10; i++) {
		for (auto& to : g[last]) {
			if (!old[to]) {
				bit[i] = to;
				break;
			}
		}
		old[last] = true;
		if (bit[i] == -1) break;
		last = bit[i];
	}
	vector<int> p(V);
	for (int i = 0; i < 10; i++) {
		if (bit[i] == -1) break;old[bit[i]] = false;
		for (auto& u : g[bit[i]]) {
			p[u] |= 1 << i;
		}
	}
	old[max_element(cnt.begin(), cnt.end()) - cnt.begin()] = false;
	for (int i = 0; i < V; i++) {
		if (old[i]) {
			for (auto& u : g[i]) {
				if (old[u] && p[i] < p[u]) edges.emplace_back(p[i] - 1, p[u] - 1);
			}
		}
	}
	InitMap(V - 12, (int) edges.size());
	for (auto&x : edges) MakeMap(x.first, x.second);
} 

Compilation message (stderr)

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:54:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   54 |   if (bit[i] == -1) break;old[bit[i]] = false;
      |   ^~
Bob.cpp:54:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   54 |   if (bit[i] == -1) break;old[bit[i]] = false;
      |                           ^~~
Bob.cpp:28:22: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   28 |  for (auto& u : g[pos]) {
      |                      ^

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