Submission #56433

#	Time	Username	Problem	Language	Result	Execution time	Memory
56433		jacobtpl	Airline Route Map (JOI18_airline)	C++14	0 / 100	736 ms	34808 KiB

Alice

#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define ii pair<int,int>
#define INF 1000000000
#define INFLL 1000000000000000100ll
#define UQ(x) (x).resize(distance((x).begin(),unique(all((x)))))
#define mid(x,y) (((x)+(y))>>1)

static vector<ii> e;
static int n,m,bits;
static int deg[2005];
static void add_directed_edge(int a,int b) {
	//printf("%d %d\n", a,b);
	deg[a]++;
	deg[b]++;
	e.pb(mp(a,b));
}
static void add_edge(int a,int b) {
	//printf("%d %d\n", a,b);
	if (rand()%2) swap(a,b);
	deg[a]++;
	deg[b]++;
	e.pb(mp(a,b));
}
static void make() {
	InitG(n+bits+2,sz(e));
	for (int i=0;i<sz(e);i++) {
		MakeG(i,e[i].first,e[i].second);
	}
}
void Alice(int N, int M, int A[], int B[]) {
	srand(83942);
	n=N;
	m=M;
	for (int i=0;i<M;i++) {
		add_edge(A[i],B[i]);
	}
	for (int i=0;i<n;i++) {
		for (int j=0;j<10;j++) {
			if (i&(1<<j)) {
				add_edge(i,N+j);
			}
		}
	}
	for (int k=1;k<=10;k++) {
		if ((1<<k)>=n) {
			bits=k;
			break;
		}
	}
	//printf("= %d\n", bits);
	for (int j=1;j<bits;j++) {
		add_edge(N+j-1,N+j);
	}
	for (int i=0;i<n;i++) {
		add_directed_edge(N+bits,i);
		add_directed_edge(N+bits+1,i);
	}
	//add_directed_edge(N+bits,N+bits+1);
	add_directed_edge(N+bits+1,N);
	make();
}

Bob

#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define ii pair<int,int>
#define INF 1000000000
#define INFLL 1000000000000000100ll
#define UQ(x) (x).resize(distance((x).begin(),unique(all((x)))))
#define mid(x,y) (((x)+(y))>>1)

static int v,u,n,bits;
static int out[2005];
static int r1=-1,r2=-1,head=-1;
static set<int> mark;
static vector<int> h;
static vector<ii> edge;
static vector<int> adj[2005];
static bool vis[2005];
void dfs(int x) {
	//printf("== %d\n", x);
	vis[x]=1;
	h.pb(x);
	for (int y:adj[x]) {
		if (vis[y]) continue;
		if (mark.find(y)==mark.end()) continue;
		dfs(y);
	}
}
static int idx[2005];
static void add_edge(int a,int b) {
	edge.pb(mp(a,b));
}
static void answer() {
	InitMap(n,sz(edge));
	for (ii x:edge) {
		MakeMap(x.first,x.second);
	}
}
static bool ingraph(int x) {
	if (x==r1 || x==r2) return 0;
	if (mark.find(x)!=mark.end()) return 0;
	return 1;
}
void Bob( int V, int U, int C[], int D[] ){
	v=V;
	u=U;
	for (int k=1;k<=10;k++) {
		if ((1<<k)>=(v-k-2)) {
			bits=k;
			break;
		}
	}
	n=v-bits-2;
	//printf("= %d\n", bits);
	for (int i=0;i<u;i++) {
		adj[C[i]].pb(D[i]);
		adj[D[i]].pb(C[i]);
		out[C[i]]++;
	}
	for (int i=0;i<v;i++) {
		//printf("* %d\n", out[i]);
		if (out[i]==n) {
			//assert(r1==-1);
			r1=i;
		}
		if (out[i]==n+1) {
			//assert(r2==-1);
			r2=i;
		}
	}
	assert(r1!=-1);
	assert(r2!=-1);
	for (int i=0;i<v;i++) mark.insert(i);
	mark.erase(r1);
	mark.erase(r2);
	for (int x:adj[r1]) {
		mark.erase(x);
	}
	assert(sz(mark)==bits);
	for (int x:adj[r2]) {
		if (mark.find(x)!=mark.end()) {
			head=x;
		}
	}
	assert(head!=-1);
	dfs(head);
	//printf("%d %d %d\n", r1,r2,head);
	assert(sz(h)==bits);
	for (int i=0;i<bits;i++) {
		for (int x:adj[h[i]]) {
			if (!ingraph(x)) continue;
			idx[x]|=(1<<i);
		}
	}
	for (int i=0;i<v;i++) {
		if (!ingraph(i)) continue;
		for (int x:adj[i]) {
			if (!ingraph(x)) continue;
			if (x>i) {
				add_edge(idx[i],idx[x]);
			}
		}
	}
	answer();
}

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