Submission #1100215

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100215		Pekiban	Airline Route Map (JOI18_airline)	C++17	100 / 100	681 ms	39972 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<array<int, 2>> t;
	for (int i = 0; i < m; ++i)	t.pb({A[i], B[i]});
	for (int i = 0; i < n; ++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+i, n+3+i});
	for (int i = 0; i < 10; ++i)	t.pb({n, n+2+i});
	for (int i = 0; i < n+12; ++i) {
		if (i != n && i != n+1)	t.pb({i, n+1});
	}
	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];
bool vis[N];
void Bob(int V, int U, int C[], int D[]){
	int n = V - 12, x = 0;
	for (int i = 0; i < U; ++i) {
		g[C[i]].pb(D[i]);
		g[D[i]].pb(C[i]);
	}
	for (int i = 0; i < V; ++i) {
		if (g[i].size() == V-2) {
			fill(vis, vis+V, 0);
			for (auto x : g[i])	vis[x] = 1;
			for (int j = 0; j < V; ++j) {
				if (!vis[j] && j != i)	x = j;
			}
			
		}
	}
	int z = -1;
	for (auto y : g[x]) {
		int c = 0;
		for (auto i : g[y]) {
			if (find(g[x].begin(), g[x].end(), i) != g[x].end()) {
				c++;
			}
		}
		if (c == 1 && z == -1)	z = y;
		if (c == 1 && z != -1 && g[y].size() > g[z].size())	z = y;
	}
	fill(vis, vis+V, 0);
	int c = 0;
	while (1) {
		vis[z] = 1;
		for (auto y : g[z])	f[y] += (1 << c);
		int Y = -1;
		for (auto y : g[z]) {
			if (find(g[x].begin(), g[x].end(), y) != g[x].end() && !vis[y]) {
				Y = y;
				break;
			}
		}
		if (Y == -1)	break;
		z = Y, ++c;
	}
	vector<array<int, 2>> vr;
	for (int i = 0; i < V; ++i) {
		if (i == x || g[i].size() == V-2 || find(g[i].begin(), g[i].end(), x) != g[i].end())	continue;
		for (auto t : g[i]) {
			if (f[t] < n && f[i] < f[t] && find(g[t].begin(), g[t].end(), x) == g[t].end()) {
				vr.pb({f[i], f[t]});
			}
		}
	}
	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:22: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]
   22 |  for (int i = 0; i < t.size(); ++i) {
      |                  ~~^~~~~~~~~~

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:18:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   18 |   if (g[i].size() == V-2) {
      |       ~~~~~~~~~~~~^~~~~~
Bob.cpp:55:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |   if (i == x || g[i].size() == V-2 || find(g[i].begin(), g[i].end(), x) != g[i].end()) continue;
      |                 ~~~~~~~~~~~~^~~~~~

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