Submission #469459

#	Time	Username	Problem	Language	Result	Execution time	Memory
469459		errorgorn	Airline Route Map (JOI18_airline)	C++17	37 / 100	814 ms	31816 KiB

Alice

#include "Alicelib.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bugz

void Alice( int n, int m, int a[], int b[] ){
	int arr[10][10]={
		{0,0,0,0,0,0,0,0,1,0},	
		{0,0,1,0,0,0,1,0,0,0},	
		{0,0,0,1,0,0,0,0,0,0},	
		{0,0,0,0,1,1,0,0,0,0},	
		{0,0,0,0,0,1,0,0,0,0},	
		{0,0,0,0,0,0,0,1,0,0},	
		{0,0,0,0,0,0,0,1,1,1},	
		{0,0,0,0,0,0,0,0,1,1},	
		{0,0,0,0,0,0,0,0,0,1},	
		{0,0,0,0,0,0,0,0,0,0}	
	};
	
	vector<int> id;
	int val[1024];
	rep(x,0,1024) if (__builtin_popcount(x)<9) id.pub(x);
	rep(x,0,sz(id)) val[id[x]]=x;
	
	vector<ii> v;
	
	rep(x,0,10) rep(y,0,10) if (arr[x][y]) v.pub({n+x,n+y});
	
	rep(x,0,n+10) v.pub({n+10,x});
	rep(x,0,n) v.pub({n+11,x});
	
	rep(x,0,m) v.pub({a[x],b[x]});
	
	rep(x,0,n){
		rep(y,0,10) if (id[x]&(1<<y)) v.pub({x,n+y});
	}
	
	InitG(n+12,sz(v));
	rep(x,0,sz(v)) MakeG(x,v[x].fi,v[x].se);
}

Bob

#include "Boblib.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

bool grid[1030][1030];
int ord[1030];

void Bob( int n, int m, int c[], int d[] ){
	int arr[10][10]={
		{0,0,0,0,0,0,0,0,1,0},	
		{0,0,1,0,0,0,1,0,0,0},	
		{0,0,0,1,0,0,0,0,0,0},	
		{0,0,0,0,1,1,0,0,0,0},	
		{0,0,0,0,0,1,0,0,0,0},	
		{0,0,0,0,0,0,0,1,0,0},	
		{0,0,0,0,0,0,0,1,1,1},	
		{0,0,0,0,0,0,0,0,1,1},	
		{0,0,0,0,0,0,0,0,0,1},	
		{0,0,0,0,0,0,0,0,0,0}	
	};
	
	vector<int> id;
	int val[1024];
	rep(x,0,1024) if (__builtin_popcount(x)<9) id.pub(x);
	rep(x,0,sz(id)) val[id[x]]=x;
	
	rep(x,0,m){
		grid[c[x]][d[x]]=true;
		grid[d[x]][c[x]]=true;
	}
		
	int idx=-1;
	int mx=0;
	
	rep(x,0,n){
		int deg=0;
		rep(y,0,n) if (grid[x][y]) deg++;
		
		if (deg>mx){
			mx=deg;
			idx=x;
		}
	}
	
	//cout<<mx<<" "<<idx<<endl;	
	int idx2;
	rep(x,0,n) if (x!=idx && !grid[idx][x]) idx2=x;
	//cout<<idx2<<endl;
	
	vector<int> ids;
	rep(x,0,n) if (x!=idx2 && x!=idx && !grid[idx2][x]) ids.pub(x);
	
	sort(all(ids));
	//for (auto &it:ids) cout<<it<<" "; cout<<endl;
	
	do{
		bool can=true;
		rep(x,0,10) rep(y,x+1,10){
			if (arr[x][y]!=grid[ids[x]][ids[y]]){
				can=false;
				goto end;
			}	
		}
		
		end:;
		
		if (can) break;
	} while (next_permutation(all(ids)));
	
	//for (auto &it:ids) cout<<it<<" "; cout<<endl;
	
	rep(x,0,n) if (x!=idx && x!=idx2){
		bool can=true;
		rep(y,0,sz(ids)) if (x==ids[y]) can=false;
		if (can){
			int num=0;
			rep(y,0,10) if (grid[x][ids[y]]) num|=(1<<y);
			
			ord[num]=x;		
		}
	}
	
	vector<ii> ans;
	rep(x,0,n-12) rep(y,x+1,n-12){
		if (grid[ord[val[x]]][ord[val[y]]]) ans.pub({x,y});
	}
	
	InitMap(n-12,sz(ans));
	for (auto &it:ans) MakeMap(it.fi,it.se);
	
}

Compilation message (stderr)

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:46:6: warning: variable 'val' set but not used [-Wunused-but-set-variable]
   46 |  int val[1024];
      |      ^~~

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:98:28: warning: 'idx2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |  rep(x,0,n) if (x!=idx && x!=idx2){
      |                           ~^~~~~~

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