Submission #61008

#	Time	Username	Problem	Language	Result	Execution time	Memory
61008		Benq	Airline Route Map (JOI18_airline)	C++11	100 / 100	788 ms	30840 KiB

Alice

#include "Alicelib.h"

#include <cassert>
#include <cstdio>

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;


void Alice( int N, int M, int A[], int B[] ){
	vpi ed;
	F0R(i,M) ed.pb({A[i],B[i]});
	F0R(i,N+10) ed.pb({i,N+11});
	F0R(i,10) ed.pb({N+i,N+10});
	F0R(i,9) ed.pb({N+i,N+i+1});
	ed.pb({N+1,N+3}); 
	F0R(i,N) F0R(j,10) if (i&(1<<j)) ed.pb({i,N+j});

	InitG(N+12,sz(ed));
	F0R(i,sz(ed)) MakeG(i,ed[i].f,ed[i].s);
}

Bob

#include "Boblib.h"

#include <cassert>
#include <cstdio>

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;


int key[1024], pos[1024], ST = -1, st = -1;
int zero, bad[1024];
vi adj[1024], adj2[1024];
bool ADJ[1024][1024];

void dfs(int cur, int ind, int pre) {
	key[ind] = cur;
	for (int i: adj2[cur]) if (i != pre) dfs(i,ind+1,cur);
}

void Bob( int V, int U, int C[], int D[] ){
	F0R(i,U) {
		adj[C[i]].pb(D[i]);
		adj[D[i]].pb(C[i]);
		ADJ[C[i]][D[i]] = ADJ[D[i]][C[i]] = 1;
	}
	F0R(i,V) key[i] = -1;
	F0R(i,V) if (sz(adj[i]) == V-2) ST = i;
	F0R(i,V) if (i != ST && !ADJ[ST][i]) st = i;

	vi posi;
	F0R(i,V) if (ADJ[st][i]) posi.pb(i);
	for (int i: posi) for (int j: posi) if (ADJ[i][j]) adj2[i].pb(j);
	for (int i: posi) if (sz(adj2[i]) == 1 && sz(adj2[adj2[i][0]]) == 3) zero = i;
	for (int i: posi) if (sz(adj2[i]) == 3) {
		for (int j: adj2[i]) if (sz(adj2[j]) == 3) {
			adj2[i].erase(find(all(adj2[i]),j));
			adj2[j].erase(find(all(adj2[j]),i));
			break;
		}
	}
	dfs(zero,0,-1);
	bad[st] = bad[ST] = 1;
	for (int i: posi) bad[i] = 1;
	F0R(i,V) if (!bad[i]) {
		int p = 0;
		F0R(j,10) if (ADJ[i][key[j]]) p ^= 1<<j;
		pos[p] = i;
	}

    vpi ed;
	F0R(i,V-12) FOR(j,i+1,V-12) if (ADJ[pos[i]][pos[j]]) ed.pb({i,j});
	InitMap( V-12, sz(ed));
	for (auto a: ed) MakeMap(a.f,a.s);
}

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