Submission #372297

#	Time	Username	Problem	Language	Result	Execution time	Memory
372297		hoaphat1	Airline Route Map (JOI18_airline)	C++17	0 / 100	704 ms	35168 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);
	}
	for (int i = 1; i <= 10; i++) edges.emplace_back(N + i - 1, N + i);
	InitG(N + 12, (int) edges.size());
	for (int i = 0; i < (int) edges.size(); i++) MakeG(i, edges[i].first, edges[i].second);
}
/*
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 = max_element(cnt.begin(), cnt.end()) - cnt.begin();
	vector<bool> old(V);
	for (auto& u : g[pos]) {
		old[u] = true;
	}
	vector<int> bit(10, -1);
	for (int i = 0; i < V; i++) {
		if (i != pos && !old[i]) {
			if ((int) g[i].size() == 1) continue;
			int num = 0;
			for (auto& u : g[i]) {
				if (!old[u]) {
					++num;
				}
			}
			if (num == 1) {
				assert(bit[0] == -1);
				bit[0] = i;
			}
		}
	}
	for (int i = 1; i < 10; i++) {
		old[bit[i-1]] = true;
		for (auto& to : g[bit[i-1]]) {
			if (!old[to]) {
				bit[i] = to;
				break;
			}
		}
		assert(bit[i] != -1);
	}
	vector<int> p(V);
	for (int i = 0; i < 10; i++) old[bit[i]] = false;
	for (int i = 0; i < 10; i++) {
		for (auto& u : g[bit[i]]) {
			p[u] |= 1 << i;
		}
	}
	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);
} */

/*int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n = 100;
	int* a = paint(n);
	//for (int i = 0; i <= n; i++) cout << a[i] <<" ";cout << endl;
	mt19937 rgn(chrono::steady_clock::now().time_since_epoch().count());
	for (int i = 0; i < 7; i++) {
		int pos = rgn() % n;
		int c[a[n]];
		for (int j = 0; j < a[n]; j++) {
			c[j] = (pos + j >= n ? -1 : a[pos + j]);
		}
		cout << pos << endl;
		cout << find_location(n, c) << endl;
	}
}*/

Bob

#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);
	}
	for (int i = 1; i <= 10; i++) edges.emplace_back(N + i - 1, N + i);
	InitG(N + 12, (int) edges.size());
	for (int i = 0; i < (int) edges.size(); i++) MakeG(i, edges[i].first, edges[i].second);
}
*/
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 = max_element(cnt.begin(), cnt.end()) - cnt.begin();
	vector<bool> old(V);
	for (auto& u : g[pos]) {
		old[u] = true;
	}
	vector<int> bit(10, -1);
	for (int i = 0; i < V; i++) {
		if (i != pos && !old[i]) {
			if ((int) g[i].size() == 1) continue;
			int num = 0;
			for (auto& u : g[i]) {
				if (!old[u]) {
					++num;
				}
			}
			if (num == 1) {
				assert(bit[0] == -1);
				bit[0] = i;
			}
		}
	}
	for (int i = 1; i < 10; i++) {
		old[bit[i-1]] = true;
		for (auto& to : g[bit[i-1]]) {
			if (!old[to]) {
				bit[i] = to;
				break;
			}
		}
		assert(bit[i] != -1);
	}
	vector<int> p(V);
	for (int i = 0; i < 10; i++) old[bit[i]] = false;
	for (int i = 0; i < 10; i++) {
		for (auto& u : g[bit[i]]) {
			p[u] |= 1 << i;
		}
	}
	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);
} 

/*int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n = 100;
	int* a = paint(n);
	//for (int i = 0; i <= n; i++) cout << a[i] <<" ";cout << endl;
	mt19937 rgn(chrono::steady_clock::now().time_since_epoch().count());
	for (int i = 0; i < 7; i++) {
		int pos = rgn() % n;
		int c[a[n]];
		for (int j = 0; j < a[n]; j++) {
			c[j] = (pos + j >= n ? -1 : a[pos + j]);
		}
		cout << pos << endl;
		cout << find_location(n, c) << endl;
	}
}*/

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