Submission #45141

#	Time	Username	Problem	Language	Result	Execution time	Memory
45141		reality	Airline Route Map (JOI18_airline)	C++17	100 / 100	776 ms	60936 KiB

Alice

#include "Alicelib.h"
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}

const int NN = (int)(1e6) + 5;

int deg[NN];

void Alice( int N, int M, int A[], int B[] ){
	vector < pii > edges;
	for (int i = 0;i < N;++i)
		edges.pb(mp(N,i));
	for (int i = 0;i < N;++i)
		for (int j = 0;j < 10;++j)
			if ((i >> j) & 1)
				edges.pb(mp(i,N + 1 + j));
	for (int i = 0;i + 1 < 10;++i)
		edges.pb(mp(i + N + 1,i + N + 2));
	for (int i = 0;i < M;++i)
		edges.pb(mp(A[i],B[i]));
	for (int i = 0;i < N + 11;++i)
		if (i != N)
			edges.pb(mp(N + 11,i));
	for (auto it : edges)
		++deg[it.fi],++deg[it.se];
	InitG(N + 12,edges.size());
	for (int i = 0;i < (edges.size());++i)
		MakeG(i,edges[i].fi,edges[i].se);
}

Bob

#include "Boblib.h"
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}

const int NN = (int)(1e6) + 5;

vi g[NN];

int G[2048][2048];

int p[NN];

void Bob( int V, int U, int C[], int D[] ){
	int n = V - 12;
	for (int i = 0;i < U;++i)
		g[C[i]].pb(D[i]),g[D[i]].pb(C[i]),G[D[i]][C[i]] = G[C[i]][D[i]] = 1;
	int aux = -1;
	vi ps;
	for (int i = 0;i < V;++i)
		if (g[i].size() == V - 2)
			ps.pb(i);
	int sep = -1;
	for (auto pp : ps) {
		int lc = -1;
		for (int i = 0;i < V;++i)
			if (!G[pp][i] && i != aux && g[i].size() == n)
				lc = i;
		if (lc != -1) {
			sep = lc;
			aux = pp;
			break;
		}
	}
	int pw2 = -1;
	for (int i = 0;i < V;++i)
		if (i != sep && i != aux && !G[sep][i] && (pw2 == -1 || g[pw2].size() > g[i].size()))
			pw2 = i;
	vi p2;
	p2.pb(pw2);
	set < int > was;
	was.insert(pw2);
	was.insert(aux);
	was.insert(sep);
	for (int t = 0;t < 9;++t) {
		for (auto it : g[p2.back()]) 
			if (!was.count(it) && !G[sep][it]) {
				p2.pb(it);
				was.insert(it);
				break;
			}
	}
	reverse(all(p2));
	for (int t = 0;t < 10;++t) {
		for (auto it : g[p2[t]])
			if (G[sep][it])
				p[it] += (1 << t);
	}
	vector < pii > edges;
	for (auto u : g[sep])
		for (auto v : g[u])
			if (G[sep][v] && u < v)
				edges.pb(mp(p[u],p[v]));
	InitMap(n,edges.size());
	for (auto it : edges)
		MakeMap(it.fi,it.se);
}

Compilation message (stderr)

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

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:33:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (g[i].size() == V - 2)
       ~~~~~~~~~~~~^~~~~~~~
Bob.cpp:39:45: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (!G[pp][i] && i != aux && g[i].size() == n)
                                 ~~~~~~~~~~~~^~~~

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