Submission #1100137

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100137		Pekiban	Airline Route Map (JOI18_airline)	C++17	0 / 100	365 ms	29320 KiB

Alice

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

using namespace std;
#define pb push_back

mt19937 rng(time(0));
void Alice(int n, int m, int A[], int B[]){
	vector<int> p = {7, 6, 4, 0, 3, 1, 9, 2, 8, 5};
    vector<array<int, 2>> t;
	for (int i = 0; i < m; ++i)	t.pb({A[i], B[i]});
	for (int i = 0; i < n+2; ++i) {
		for (int j = 0; j < 10; ++j) {
			if ((i >> j) & 1)	t.pb({i, n + 2 + j});
		}
	}
	for (int i = 0; i < 9; ++i) {
		t.pb({n + 2 + p[i], n + 2 + p[i+1]});
		if (i + 3 < 10)	t.pb({n + 2 + p[i], n + 2 + p[i+3]});
	}
	for (int i = 0; i < n; ++i) {
		if (rng() & 1)	t.pb({n, i});
		if (rng() & 1)	t.pb({n+1, i});
	}
	InitG(n + 12, t.size());
	for (int i = 0; i < t.size(); ++i) {
		MakeG(i, t[i][0], t[i][1]);
	}
}

// https://www.youtube.com/watch?v=vUqzpujUU7c zeta z orz

Bob

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

using namespace std;
#define pb push_back

const int N = 1024;
vector<int> g[N];
int f[N];
void Bob(int V, int U, int C[], int D[]){
	int n = V - 12;
	for (int i = 0; i < U; ++i) {
		g[C[i]].pb(D[i]);
		g[D[i]].pb(C[i]);
	}
	vector<int> p = {7, 6, 4, 0, 3, 1, 9, 2, 8, 5};
	vector<vector<int>> av;
	for (int j = 0; j < 10; ++j) {
		int c = (1 <= j) + (3 <= j) + (j <= 8) + (j <= 6);
		for (int i = 0; i < n+2; ++i) {
			if ((i >> p[j]) & 1)	++c;
		}
		if (j) {
			vector<vector<int>> t;
			for (auto &x : av) {
				for (auto &y : g[x.back()]) {
					if (g[y].size() == c) {
						bool ok = 1;
						for (auto &z : x) {
							if (z == y) {
								ok = 0;
								break;
							}
						}
						if (ok) {
							t.pb(x);
							t.back().pb(y);
						}
					}
				}
				
			}
			av = t;
		}
		else {
			for (int i = 0; i < V; ++i) {
				if (g[i].size() == c)	av.pb({i});
			}
		}
	}
	for (int i = 0; i < 10; ++i) {
		for (auto y : g[av[0][i]]) {
			f[y] += (1 << p[i]);
		}
	}
	vector<array<int, 2>> vr;
	for (int i = 0; i < V; ++i) {
		if (f[i] >= n)	continue;
		for (auto x : g[i]) {
			if (f[x] < n && f[i] < f[x]) {
				vr.pb({f[i], f[x]});
			}
		}
	}
	InitMap(n, vr.size());
	for (auto [x, y] : vr)	{
		MakeMap(x, y);
	}
}

Compilation message (stderr)

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:26:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for (int i = 0; i < t.size(); ++i) {
      |                  ~~^~~~~~~~~~

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:27:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |      if (g[y].size() == c) {
      |          ~~~~~~~~~~~~^~~~
Bob.cpp:47:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |     if (g[i].size() == c) av.pb({i});
      |         ~~~~~~~~~~~~^~~~

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