Submission #260836

#	Time	Username	Problem	Language	Result	Execution time	Memory
260836		arnold518	Airline Route Map (JOI18_airline)	C++14	88 / 100	723 ms	34192 KiB

Alice

#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
static int N, M, *A, *B;
static vector<pii> E;
 
void Alice(int _N, int _M, int _A[], int _B[])
{
	N=_N; M=_M; A=_A; B=_B;
 
	for(int i=0; i<M; i++)
	{
		int u=A[i], v=B[i];
		E.push_back({u, v});
	}
 
	for(int i=0; i<10; i++)
	{
		for(int j=0; j<N; j++)
		{
			if(!(j&(1<<i))) E.push_back({N+i, j});
		}
	}
	for(int i=N; i<N+10; i++) E.push_back({N+10, i});
	for(int i=N+1; i<N+10; i++) E.push_back({i-1, i});
	E.push_back({N+11, N+10});
	E.push_back({N, N+12});
	E.push_back({N+12, N+13});
 
	InitG(N+14, E.size());
	for(int i=0; i<E.size(); i++) MakeG(i, E[i].first, E[i].second);
}

Bob

#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
static const int MAXN = 1100;
 
static int V, U, *C, *D;
static vector<int> adj[MAXN+10];
static int N, deg[MAXN+10], A[MAXN+10], B[MAXN+10];
static vector<pii> E;
static int vis[MAXN+10], adj2[MAXN+10][MAXN+10];
 
void Bob(int _V, int _U, int _C[], int _D[])
{
	V=_V; U=_U; C=_C; D=_D; N=V-14;
	for(int i=0; i<U; i++)
	{
		int u=C[i], v=D[i];
		adj[u].push_back(v);
		adj[v].push_back(u);
		deg[u]++; deg[v]++;
		adj2[u][v]=adj2[v][u]=1;
	}
 	
 	int P=-1, Q=-1, R=-1, S=-1;
 	for(int i=0; i<N+14; i++) if(adj[i].size()==1 && deg[adj[i].front()]==11) P=i;
 	for(int i=0; i<N+14; i++) if(adj[i].size()==1 && deg[adj[i].front()]==2) R=i;

 	Q=adj[P].front(); S=adj[R].front();
 	vis[P]=1; vis[Q]=1; vis[R]=1; vis[S]=1;

 	vector<int> VV;
 	for(auto it : adj[Q])
 	{
 		if(vis[it]) continue;
 		vis[it]=2;
 	}
 	
 	int now;
 	if(adj[S][0]==R) now=adj[S][1];
 	else now=adj[S][0];

 	while(1)
 	{
 		VV.push_back(now);
 		vis[now]=1;
 		bool flag=false;
 		for(auto nxt : adj[Q]) if(adj2[now][nxt] && vis[nxt]==2) { now=nxt; flag=true; break; }
 		if(!flag) break;
 	}

 	for(int i=0; i<10; i++)
 	{
 		for(int j=0; j<N+14; j++)
 		{
 			if(vis[j]) continue;
 			if(!adj2[VV[i]][j]) A[j]+=(1<<i);
 		}
 	}

 	for(int i=0; i<N+14; i++)
 	{
 		if(vis[i]) continue;
 		for(int j=i+1; j<N+14; j++)
 		{
 			if(vis[j]) continue;
 			if(!adj2[i][j]) continue;
 			E.push_back({A[i], A[j]});
 		}
 	}

 	InitMap(N, E.size());
 	for(auto it : E) MakeMap(it.first, it.second);
}

Compilation message (stderr)

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

Bob.cpp:13:41: warning: 'B' defined but not used [-Wunused-variable]
 static int N, deg[MAXN+10], A[MAXN+10], B[MAXN+10];
                                         ^

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