Submission #567666

#	Time	Username	Problem	Language	Result	Execution time	Memory
567666		zaneyu	Airline Route Map (JOI18_airline)	C++14	100 / 100	553 ms	29356 KiB

Alice

#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
//order_of_key #of elements less than x
// find_by_order kth element
typedef long long int ll;
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define ld long double
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
namespace alice{
	///put all "global" variables for alice inside here
	int aliceU = 3;
	int aliceV = 2;
};

void Alice(int n, int m, int A[], int B[] ){
	//using namespace alice;
	
	//InitG(aliceU, aliceV);
	vector<pii> v;
	REP(i,m){
		v.pb({A[i],B[i]});
	}
	REP(i,n){
		REP(j,10){
			if(i&(1<<j)){
				v.pb({n+j+1,i});
			}
		}
	}
	REP(i,n+11) if(i!=n) v.pb({i,n});
	REP1(i,10) v.pb({n+11,n+i});
	REP1(i,9) v.pb({n+i,n+i+1});
	InitG(n+12,sz(v));
	REP(i,sz(v)) MakeG(i,v[i].f,v[i].s);
}

Bob

#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
//order_of_key #of elements less than x
// find_by_order kth element
typedef long long int ll;
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define ld long double
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
///poor man's communication problem
///do not include any global variables, use only local variables and namespaced global variables.
///If you wish to use 'global' variables, use the namespace for alice and bob, and do not let alice read bob's variables and vice versa

namespace bob{
	///put all "global" variables for bob inside here
	vector<int> v[2005];
	bool hv[2005];
	int mp[2005];
};
void Bob( int U, int V, int C[], int D[] ){
	using namespace bob;
	int n=U-12;
	REP(i,V){
		v[C[i]].pb(D[i]);
		v[D[i]].pb(C[i]);
		//cout<<C[i]<<' '<<D[i]<<'\n';
	}
	REP(i,U) mp[i]=-1;
	int p=0;
	REP(i,U){
		if(sz(v[i])>sz(v[p])) p=i;
	}
	mp[p]=n;
	for(int x:v[p]) hv[x]=1;
	int z;
	REP(i,U) if(!hv[i] and i!=p) z=i;
	REP(i,U) hv[i]=0;
	p=-1;
	mp[z]=n+11;
	for(int x:v[z]){
		hv[x]=1;
	}
	for(int x:v[z]){
		int cnt=0;
		for(int a:v[x]){
			if(hv[a]) ++cnt;
		}
		if(cnt==1){
			if(p==-1 or sz(v[p])>sz(v[x])) p=x;
		}
	}
	int pv=-1;
	REP(i,10){
		mp[p]=n+10-i;
		int tmp=p;
		for(int x:v[p]){
			if(hv[x] and x!=pv){
				p=x;
				break;
			}
		}
		pv=tmp;
	}
	//REP(i,U) cout<<mp[i]<<' ';
	//cout<<'\n';
	REP(i,U){
		if(mp[i]!=-1) continue;
		int cur=0;
		for(int x:v[i]){
			if(mp[x]!=-1 and mp[x]>n){
				cur|=(1<<(mp[x]-n-1));
			}
		}
		mp[i]=cur;
	}
	vector<pii> ans;
	REP(i,V){
		if(mp[C[i]]<n and mp[D[i]]<n) ans.pb({mp[C[i]],mp[D[i]]});
	}
	InitMap(n,sz(ans));
	for(auto x:ans) MakeMap(x.f,x.s);
}

Compilation message (stderr)

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:45:6: warning: 'z' may be used uninitialized in this function [-Wmaybe-uninitialized]
   45 |  int z;
      |      ^

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