Submission #955919

#	Time	Username	Problem	Language	Result	Execution time	Memory
955919		Maaxle	Airline Route Map (JOI18_airline)	C++17	100 / 100	565 ms	50280 KiB

Alice

#include <bits/stdc++.h>
#include "Alicelib.h"

#define range(it, a, b) for (ll it = a; it < b; it++)
#define all(x) begin(x), end(x)
#define ll long long
#define ull unsigned long long
#define INF64 ((ll) 1 << 62)
#define INF32 (1 << 30)
#define mset multiset
#define uset unordered_set
#define umap unordered_map 
#define pqueue priority_queue 
#define ptr(A) shared_ptr<A>

using namespace std;

ll n, _to, _ax;
vector<vector<ll>> adj;

ll bit_node(ll b) { return _ax+1+b; }

void Alice( int N, int M, int A[], int B[] ){
	n = N;
	_to = n;
	_ax = _to+1;
	adj.resize(n + 12);

	ll cnt = 0;
	range(i, 0, n) {
		adj[_to].push_back(i);
		cnt++;
		range(b, 0, 10) {
			if (i & (1 << b)) {
				adj[bit_node(b)].push_back(i);
				cnt++;
			}
		}
	}
	range(i, 0, 9) {
		adj[bit_node(i)].push_back(bit_node(i+1));
		cnt++;
	}
	range(i, 0, M) {
		adj[A[i]].push_back(B[i]);
		cnt++;
	}
	adj[_ax].push_back(_to);
	cnt++;
	
	// cout << "V = " << N+12 << " U = " << cnt << '\n';
	InitG(N+12, cnt);
	cnt = 0;
	range(i, 0, n + 12) {
		for (ll& j : adj[i]) {
			// cout << cnt << ' ' << i << ' ' << j << '\n';
			MakeG(cnt++, i, j);	
		}		
	}
}

Bob

#include "Boblib.h"
#include <bits/stdc++.h>

#define range(it, a, b) for (ll it = a; it < b; it++)
#define all(x) begin(x), end(x)
#define ll long long
#define ull unsigned long long
#define INF64 ((ll) 1 << 62)
#define INF32 (1 << 30)
#define mset multiset
#define uset unordered_set
#define umap unordered_map 
#define pqueue priority_queue 
#define ptr(A) shared_ptr<A>

using namespace std;

ll N;
ll ax, to;
vector<vector<ll>> alice_adj;
vector<bool> not_bit;
vector<ll> cast;

void translate_nodes(ll node, ll bit, ll last_node) {
	for (ll i : alice_adj[node]) {
		if (!not_bit[i] && i != last_node) {
			translate_nodes(i, bit+1, node);
			continue;
		}
		cast[i] += (1 << bit);
	}
}

void Bob( int V, int U, int C[], int D[]){
	N = V - 12;
	alice_adj.resize(V);
	not_bit.resize(V);
	cast.resize(V);

	range(i, 0, U) {
		alice_adj[C[i]].push_back(D[i]);
		alice_adj[D[i]].push_back(C[i]);
	}

	range(i, 0, V) {
		if (alice_adj[i].size() == 1 && alice_adj[alice_adj[i][0]].size() == N+1) {
			ax = i;
			to = alice_adj[i][0];
			break;
		}
	}

	not_bit[to] = 1;
	for (ll& i : alice_adj[to])
		not_bit[i] = 1;
	
	ll znode = -1, zgrade = 0;
	range(i, 0, V) {
		if (!not_bit[i]) {
			ll cnt = 0;
			for (ll& k : alice_adj[i]) {
				if (!not_bit[k]) {
					if (++cnt > 1)
						break;
				}
			}
			if (cnt == 1 && zgrade < alice_adj[i].size()) {
				znode = i;
				zgrade = alice_adj[i].size();
			}
		}
	}
	translate_nodes(znode, 0, -1);

	vector<pair<ll, ll>> ans;
	range(i, 0, V) {
		if (not_bit[i] && i != to && i != ax) {
			for (ll& k : alice_adj[i]) {
				if (not_bit[k] && k != to && k != ax && cast[i] < cast[k]) {
					ans.push_back({cast[i], cast[k]});
				}
			}
		}
	}
	InitMap(N, ans.size());
	for (pair<ll, ll>& it : ans) 
		MakeMap(it.first, it.second);
}

Compilation message (stderr)

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:46:69: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   46 |   if (alice_adj[i].size() == 1 && alice_adj[alice_adj[i][0]].size() == N+1) {
      |                                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
Bob.cpp:67:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |    if (cnt == 1 && zgrade < alice_adj[i].size()) {
      |                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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