Submission #599102

#	Time	Username	Problem	Language	Result	Execution time	Memory
599102		Soumya1	Airline Route Map (JOI18_airline)	C++17	100 / 100	777 ms	24968 KiB

Alice

#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
void Alice(int n, int m, int U[], int V[] ){
	vector<pair<int, int>> edges;
	for (int i = 0; i < m; i++) {
		edges.push_back({U[i], V[i]});
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 10; j++) {
			if ((i >> j) & 1) {
				edges.push_back({i, n + j});
			}
		}
	}
	for (int i = 1; i < 10; i++) {
		edges.push_back({n + i, n + i - 1});
	}
	for (int i = 0; i < n; i++) {
		edges.push_back({i, n + 10});
	}
	for (int i = 0; i < 10; i++) {
		edges.push_back({n + i, n + 10});
		edges.push_back({n + i, n + 11});
	}
	InitG(n + 12, edges.size());
	for (int i = 0; i < edges.size(); i++) {
		MakeG(i, edges[i].first, edges[i].second);
	}
}

Bob

#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
void Bob(int V, int U, int C[], int D[]){
	int n = V - 12;
	vector<int> deg(V);
	vector<vector<bool>> ad(V, vector<bool> (V));
	for (int i = 0; i < U; i++) {
		deg[C[i]]++, deg[D[i]]++;
		ad[C[i]][D[i]] = ad[D[i]][C[i]] = true;
	}
	int s1, s2;
	for (int i = 0; i < V; i++) {
		if (deg[i] == V - 2) {
			s1 = i;
			for (int j = 0; j < V; j++) {
				if (j != i && !ad[j][i]) s2 = j;
			}
			break;
		}
	}
	vector<bool> actual(V, true);
	actual[s1] = actual[s2] = false;
	int start = -1;
	vector<int> value(V), id(V);
	for (int i = 0; i < V; i++) {
		if (ad[s2][i]) {
			actual[i] = false;
		}
	}
	vector<int> fake_deg(V);
	for (int i = 0; i < U; i++) {
		if (!actual[C[i]] && !actual[D[i]]) {
			fake_deg[C[i]]++, fake_deg[D[i]]++;
		}
	}
	for (int i = 0; i < V; i++) {
		if (i == s1 || i == s2 || actual[i]) continue;
		if (fake_deg[i] == 3 && (start == -1 || deg[i] > deg[start])) start = i;
	}
	{
		vector<bool> vis(V);
		int cur = 0;
		for (int i = 0; i < 10; i++) {
			vis[start] = true;
			value[start] = cur++;
			for (int j = 0; j < V; j++) {
				if (j == s1 || j == s2 || actual[j] || vis[j] || !ad[start][j]) continue;
				start = j;
				break;
			}
		}
		for (int i = 0; i < V; i++) {
			if (!actual[i]) continue;
			for (int j = 0; j < V; j++) {
				if (actual[j] || j == s1 || j == s2 || !ad[i][j]) continue;
				id[i] |= (1 << value[j]);
			}
		}
	}
	vector<pair<int, int>> edges;
	for (int i = 0; i < U; i++) {
		if (actual[C[i]] && actual[D[i]]) {
			edges.push_back({id[C[i]], id[D[i]]});
		}
	}
	InitMap(V - 12, edges.size());
	for (auto [a, b] : edges) {
		MakeMap(a, b);
	}
}

Compilation message (stderr)

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

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:5:6: warning: unused variable 'n' [-Wunused-variable]
    5 |  int n = V - 12;
      |      ^
Bob.cpp:56:35: warning: 's2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   56 |     if (actual[j] || j == s1 || j == s2 || !ad[i][j]) continue;
      |                                 ~~^~~~~
Bob.cpp:56:24: warning: 's1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   56 |     if (actual[j] || j == s1 || j == s2 || !ad[i][j]) continue;
      |                      ~~^~~~~

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