Submission #72792

#	Time	Username	Problem	Language	Result	Execution time	Memory
72792		shoemakerjo	Airline Route Map (JOI18_airline)	C++14	0 / 100	778 ms	34672 KiB

Alice

#include <bits/stdc++.h>
#include "Alicelib.h"
 
using namespace std;
#define maxn 1010
#define pii pair<int, int>
 
int e[12]; //store the indices for the extra guys
int deg[12]; //store the degrees for each of the extras
 
vector<pii> edges;
 
void Alice(int N, int M, int A[], int B[]) {
	if (N == 1) {
		//handle this case uniquely
		InitG(1, 0);
		return;
	}
	if (N == 2) {
		InitG(N, M);
		if (M == 1) {
			MakeG(0, 0, 1);
		}
		return;
	}
	//lol, need to push back original edges or something
	for (int i = 0; i < M; i++) {
		edges.push_back(pii(A[i], B[i]));
	}
	if (N == 3) {
		bool cad[3][3]; //current adjacent
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				cad[i][j] = false;
			}
		}
		for (int i = 0; i < M; i++) {
			cad[A[i]][B[i]] = true;
			cad[B[i]][A[i]] = true;
		}
 
		if (cad[0][1] && cad[0][2] && cad[1][2]) {
			InitG(11, 0);
			return;
		}
		if (cad[0][1] && cad[1][2]) {
			InitG(10, 0);
			return;
		}
		if (cad[0][2] && cad[1][2]) {
			InitG(9, 0);
			return;
		}
		if (cad[0][1] && cad[0][2]) {
			InitG(8, 0);
			return;
		}
		if (cad[0][2]) {
			InitG(7, 0);
			return;
		}
		if (cad[1][2]) {
			InitG(6, 0);
			return;
		}
		if (cad[0][1]) {
			InitG(5, 0);
			return;
		}
		InitG(4, 0);
		return;
	}
	//all special cases finished
	for (int i = 0; i < 12; i++) {
		e[i] = N + i; //just store it
	}
	for (int i = 0; i < N; i++) {
		edges.push_back(pii(e[11], i));
	}
	for (int i = 0; i < N; i++) {
		//connect me to everythig that one greater than me stores (oops)
		for (int j = 0; j < 10; j++) {
			if ( (i + 1) & ( 1 << j)) {
				edges.push_back(pii(e[j], i));
				deg[j]++;
			}
		}
	}
 
	edges.push_back(pii(e[11], e[10]));
	for (int i = 0; i < 9; i++) {
		if (i == 10) continue;
		edges.push_back(pii(e[10], e[i]));
	}
	if (N != 9) edges.push_back(pii(e[10], e[9]));
	else edges.push_back(pii(e[9], e[10]));
	for (int i = 1; i < 10; i++) { //create the change
		edges.push_back(pii(e[i-1], e[i]));
	}
	
 
	InitG(N+12, edges.size());
	for (int i = 0; i < edges.size(); i++) {
		MakeG(i, edges[i].first, edges[i].second);
	}
 
	/*
	cout << "ALICE EDGES" << endl;
	for (pii vp : edges) {
		cout << "-------->      " << vp.first << " " << vp.second << endl;
	}	
	cout << endl << endl;
	*/
	//i think this is finished
	
}
//call InitG with some number of nodes and edges
//cakk MakeG with pos, a, and b

Bob

#include <bits/stdc++.h>
#include "Boblib.h"
 
using namespace std;
#define edges this_is_a_bad_variable_name
#define e this_is_a_bad_variable_name2
#define dec this_is_a_bad_variable_name3
#define deg this_is_a_bad_variable_name4
#define pii pair<int, int>
//adding macros to make it compile locally
 
vector<pii> edges; //this is where we store the answers
int e[12];
int dec[1100]; //decode the nodes (what they are now vs what they should be)
int enc[1100]; //encode the nodes (opp of above)
int deg[1100];
vector<vector<int>> adj(1100);
 
void special(int v) {
	//figure it out for 3
	if (v == 4) {
		InitMap(3, 0);
		return;
	}
	if (v == 5) {
		InitMap(3, 1);
		MakeMap(0, 1);
		return;
	}
	if (v == 6) {
		InitMap(3, 1);
		MakeMap(1, 2);
		return;
	}
	if (v == 7) {
		InitMap(3, 1);
		MakeMap(0, 2);
		return;
	}
	if (v == 8) {
		InitMap(3, 2);
		MakeMap(0, 1);
		MakeMap(0, 2);
		return;
	}
	if (v == 9) {
		InitMap(3, 2);
		MakeMap(0, 2);
		MakeMap(1, 2);
		return;
	}
	if (v == 10) {
		InitMap(3, 2);
		MakeMap(0, 1);
		MakeMap(1, 2);
		return;
	}
	if (v == 11) {
		InitMap(3, 3);
		MakeMap(0, 1);
		MakeMap(0, 2);
		MakeMap(1, 2);
	}
}
 
 
void Bob(int V, int U, int C[], int D[]) {
 
//	cout << "V: " << V << endl;
 
	if (V == 1) {
		InitMap(1, 0);
		return;
	}
	if (V == 2) {
		InitMap(V, U);
		if (U == 1) MakeMap(0, 1);
		return;
	}
	if (V < 12) {
		special(V);
		return;
	}
 
	//special cases are finished
	int n = V-12;
	for (int i = 0; i < 12; i++) {
		e[i] = n+i; //same scheme as in Alice
	}
 
	//first we need to find the node that is e11, connected to all n things
//	cout << "ORIGINAL EDGES" << endl;
	for (int i = 0; i < U; i++) {
		adj[C[i]].push_back(D[i]);
		adj[D[i]].push_back(C[i]);
		deg[C[i]]++;
		// deg[D[i]]++;
//		if (C[i] == 14 || D[i] == 14) cout << "**  ";
//		cout << "    " << C[i] << " " << D[i] << endl;
 
	}
//	cout << endl << endl;
 
	int e11 = -1; //find this boy
	for (int i = 0; i < V; i++) {
		if (deg[i] == n+1) { //connected to all original plus the dummy
			e11 = i;
		}
	}
//	cout << "e11 deg: " << deg[e11] << endl;
//	cout << "e11:   " << e11 << endl; 	
	dec[e11] = e[11];
	enc[e[11]] = e11;
 
	//now that we have the node, we can just separate into o group and others
	vector<int> ogroup;
	set<int> og;
	vector<int> ext;
	set<int> isext;
	set<int> seen;
	seen.insert(e11);
	for (int val : adj[e11]) {
		seen.insert(val);
	}
	for (int i = 0; i < V; i++) {
		if (seen.find(i) == seen.end()) {
//			cout << i << " is an extra " << endl;
			ext.push_back(i);
			isext.insert(i);
		}
	}
 
	int dummy = -1; //find the guy with degree one from the extras
 
 
	for (int val : seen) {//look for the dummy
		int ed = 0; //extra degree
		for (int v2 : adj[val]) {
			if (isext.count(v2) > 0) ed++;
		}
		if (ed == 10) {
			//connect to 0 throuh 9
			dummy = val;
		}
//		cout << val << " ----- " << adj[val].size() << " " << ed << endl;
	}
//	cout << endl;
 
//	cout << "dummy: " << dummy << endl;
 
	for (int i = 0; i < V; i++) {
		if (i == dummy || i == e11 || isext.count(i)) continue;
		ogroup.push_back(i);
		og.insert(i);
	}
 
	vector<pii> d1e;
	for (int val : ext) {
		int ed = 0;
		for (int v2 : adj[val]) {
			if (isext.count(v2) > 0) {
				ed++;
			}
		}
		if (ed == 1) {
			//is an endpoint
			d1e.push_back(pii(adj[val].size()-1, val));
		}
	}
//	cout << "SZ: " << d1e.size() << endl;
	sort(d1e.begin(), d1e.end());
 
	dec[dummy] = e[10];
	enc[e[10]] = dummy;
 
	map<int, int> bm; //bitmask map
//	cout << "original Nodes: ";
//	for (int val : ogroup) cout << val << " ";
//	cout << endl;
 
	int cur = d1e[1].second;
//	cout << "CHAIN: " << cur << " ";
	bm[cur] = 0;
	for (int i = 1 ; i < 10; i++) {
		//find the next thing
		seen.insert(cur);
		int nx = -1;
		for (int val : adj[cur]) {
			if (seen.find(val) == seen.end()) {
				//is an extra vertex
				nx = val;
				break;
			}
		}
		if (nx == -1) break; //nothing more to see here
		dec[nx] = e[i];
		enc[e[i]] = nx;
 
		// if (bm.count(nx) == 0) cout << "NOOOO" << endl;
		bm[nx] = i; 
 
		cur = nx; //last part of the loop
//		cout << cur << " ";
 
	}
//	cout << endl;
 
	for (int val : ogroup) {
		int cv = 0;
		for (int nx : adj[val]) {
			if (og.find(nx) != og.end() || nx == e11) continue;
//			cout << val << ": chaining to: " << nx << endl;
//			if (bm.count(nx) == 0) cout << "       WHYYYYYY" << endl;
			int nv = bm[nx];
			cv += (1 << nv);
		}
//		cout << val << " gets: " << cv-1 << endl;
		dec[val] = cv-1; //subtract 1 b/c 0-indexed
	}
 
	for (int val : ogroup) {
		for (int nx : adj[val]) {
 
			if (og.find(nx) != og.end() && dec[val] < dec[nx]) {
				edges.push_back(pii(dec[val], dec[nx])); //decode both
//				cout << "draws an edge from " 
//					<< dec[val] << " to " << dec[nx] << endl;
			}
		}
	}
 
 
	//everything finished
	InitMap(n, edges.size());
	for (pii vp : edges) {
		MakeMap(vp.first, vp.second);
	}
 
 
}
//Initmap with n nodes and e edges

Compilation message (stderr)

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:103:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < edges.size(); i++) {
                  ~~^~~~~~~~~~~~~~

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