Submission #108810

#	Time	Username	Problem	Language	Result	Execution time	Memory
108810		tictaccat	Airline Route Map (JOI18_airline)	C++14	0 / 100	619 ms	127296 KiB

Alice

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

using namespace std;

void Alice( int N, int M, int At[], int Bt[] ){

	vector<vector<int>> adj(4*N*N + 10*N);

	for (int i = 0; i < M; i++) {
		adj[At[i]].push_back(Bt[i]);
		adj[Bt[i]].push_back(At[i]);
	}

	int c = N;
	int e = M;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j <= i; j++) {
			adj[c].push_back(i);
			adj[i].push_back(c);
			e++;
			c++;
		}
	}

	c += 20;

	for (int i = N; i < c; i++) {
		adj[c].push_back(i);
		adj[i].push_back(c);
		e++;
	}



	InitG(c+1, e);

	int k = 0;

	for (int i = 0; i <= c; i++) {
		for (int j: adj[i]) {
			if (j < i) continue;
			MakeG(k++,i,j);
		}
	}
	
}

Bob

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

using namespace std;

void Bob( int V, int U, int C[], int D[] ){

	vector<vector<int>> adj(V);

	for (int i = 0; i < U; i++) {
		adj[C[i]].push_back(D[i]);
		adj[D[i]].push_back(C[i]);
	}

	int spec = max_element(adj.begin(),adj.end(),[](vector<int> &a, vector<int> &b){return a.size() < b.size();}) - adj.begin();

	vector<bool> special(V,false);

	for (int i: adj[spec]) {
		special[i] = true;
	}

	vector<int> actual(V,-1);

	int N = 0;

	for (int i = 0; i < V; i++) {
		if (i == spec) continue;
		int c = 0;
		for (int j: adj[i]) {
			if (special[j]) c++;
		}
		if (c > 0) {
			actual[i] = c-1;
			N++;
		}
	}

//	cout << N << "\n";

	vector<pair<int,int>> el;

	for (int i = 0; i < U; i++) {
		if (actual[C[i]] != -1 && actual[D[i]] != -1) {
			el.push_back(make_pair(actual[C[i]],actual[D[i]]));
		}
	}

	InitMap(N,el.size());

	for (auto p: el) {
		MakeMap(p.first,p.second);
	}

	// InitMap( 3, 2 );
	// MakeMap( 1, 2 );
	// MakeMap( 1, 3 );
}

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