Submission #45138

#	Time	Username	Problem	Language	Result	Execution time	Memory
45138		reality	Airline Route Map (JOI18_airline)	C++17	100 / 100	2191 ms	119556 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];
	//dbg(deg[N]);
	//dbg(deg[511]);
	int mx = *max_element(deg,deg + N + 12);
	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;

static set < int > g[NN];

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]].insert(D[i]),g[D[i]].insert(C[i]);
	//for (int i = 0;i < V;++i) {
	//	dbg(i);
	//	for (auto it : g[i])
	//		cerr << it << ' ';
	//	cerr << '\n';
	//}
	int aux = -1;
	int shit = 0;
	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].count(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].count(i) && (pw2 == -1 || g[pw2].size() > g[i].size()))
			pw2 = i;
	vi p2;
	p2.pb(pw2);
	//dbg(aux);
	//dbg(sep);
	//dbg(pw2);
	//exit(0);
	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].count(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].count(it))
				p[it] += (1 << t);
	}
	vector < pii > edges;
	for (auto u : g[sep])
		for (auto v : g[u])
			if (g[sep].count(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:43:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0;i < (edges.size());++i)
                 ~~^~~~~~~~~~~~~~~~
Alice.cpp:41:6: warning: unused variable 'mx' [-Wunused-variable]
  int mx = *max_element(deg,deg + N + 12);
      ^~

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:38:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (g[i].size() == V - 2)
       ~~~~~~~~~~~~^~~~~~~~
Bob.cpp:44:51: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (!g[pp].count(i) && i != aux && g[i].size() == n)
                                       ~~~~~~~~~~~~^~~~
Bob.cpp:35:6: warning: unused variable 'shit' [-Wunused-variable]
  int shit = 0;
      ^~~~

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