Submission #44167

#	Time	Username	Problem	Language	Result	Execution time	Memory
44167		zscoder	Airline Route Map (JOI18_airline)	C++17	100 / 100	858 ms	30816 KiB

Alice

#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;

void Alice( int N, int M, int A[], int B[] )
{
	vector<ii> edges;
	for(int i=0;i<M;i++)
	{
		edges.pb(mp(A[i],B[i]));
	}
	for(int i=0;i<10;i++)
	{
		for(int j=0;j<N;j++)
		{
			if(j&(1<<i))
			{
				edges.pb(mp(N+i, j));
			}
		}
	}
	for(int j=0;j<9;j++)
	{
		edges.pb(mp(N+j, N+j+1));
	}
	for(int i=0;i<2;i++)
	{
		for(int j=0;j<10;j++)
		{
			edges.pb(mp(N+10+i, N+j));
		}
	}
	InitG(N+12, int(edges.size()));
	//cerr<<N+12<<' '<<edges.size()<<'\n';
	for(int i=0;i<edges.size();i++)
	{
		//cerr<<i<<' '<<edges[i].fi<<' '<<edges[i].se<<'\n';
		MakeG(i, edges[i].fi, edges[i].se);
	}
}

Bob

#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;

static int perm[1111];
static vector<int> adj[1111];
static ll hsh[1111];
static bool vis[1111];

void Bob( int V, int U, int C[], int D[] )
{
	for(int i=0;i<U;i++)
	{
		adj[C[i]].pb(D[i]); adj[D[i]].pb(C[i]);
	}
	const int cc = 2017;
	for(int i=0;i<V;i++)
	{
		sort(adj[i].begin(),adj[i].end());
		if(adj[i].size()==10)
		{
			for(int v:adj[i])
			{
				hsh[i]*=cc;
				hsh[i]+=v+1;
			}
		}
	}
	int idx=0; int idy=0;
	for(int i=0;i<V;i++)
	{
		if(adj[i].size()==10)
		{
			for(int j=i+1;j<V;j++)
			{
				if(adj[j].size()==10&&hsh[i]==hsh[j])
				{
					idx=i; idy=j; break;
				}
			}
		}
	}
	int bitgod[10]={};
	set<int> gods;
	for(int v:adj[idx]) gods.insert(v);
	vi pathend;
	for(int v:adj[idx])
	{
		int cnt=0;
		for(int x:gods)
		{
			cnt+=binary_search(adj[v].begin(),adj[v].end(),x);
		}
		if(cnt==1) pathend.pb(v);
	}
	assert(pathend.size()==2);
	if(adj[pathend[0]].size()<adj[pathend[1]].size()) swap(pathend[0],pathend[1]);
	bitgod[0] = pathend[0];
	vis[bitgod[0]] = 1;
	for(int i=1;i<10;i++)
	{
		int cur = bitgod[i-1];
		for(int v:adj[cur])
		{
			if(gods.find(v)!=gods.end()&&!vis[v])
			{
				bitgod[i] = v; vis[v] = 1; break;
			}
		}
	}
	memset(perm,-1,sizeof(perm));
	for(int i=0;i<V;i++)
	{
		if(gods.find(i)==gods.end()&&i!=idx&&i!=idy)
		{
			int label=0;
			for(int j=0;j<10;j++)
			{
				if(binary_search(adj[i].begin(),adj[i].end(),bitgod[j]))
				{
					label^=(1<<j);
				}
			}
			perm[i] = label;
		}
	}
	vector<ii> edges;
	for(int i=0;i<U;i++)
	{
		if(perm[C[i]]!=-1&&perm[D[i]]!=-1) edges.pb(mp(perm[C[i]],perm[D[i]]));
	}
	InitMap(V - 12, int(edges.size()));
	for(int i=0;i<edges.size();i++)
	{
		MakeMap(edges[i].fi, edges[i].se);
	}
}

Compilation message (stderr)

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:56:15: 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:114:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<edges.size();i++)
              ~^~~~~~~~~~~~~

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