Submission #236186

#	Time	Username	Problem	Language	Result	Execution time	Memory
236186		MvC	Airline Route Map (JOI18_airline)	C++11	100 / 100	772 ms	31392 KiB

Alice

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include "Alicelib.h"
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=1e5+50;
const ll mod=1e9+7;
using namespace std;
int i,j,bt[15];
vector<pair<int,int> >vc;
void Alice(int n,int m,int a[],int b[])
{
	for(i=0;i<10;i++)bt[i]=n+i;
	for(i=1;i<10;i++)vc.pb(mkp(bt[i-1],bt[i]));
	for(i=0;i<m;i++)vc.pb(mkp(a[i],b[i]));
	for(i=0;i<n;i++)for(j=0;j<10;j++)if(i&(1<<j))vc.pb(mkp(bt[j],i));
	for(i=0;i<n+10;i++)vc.pb(mkp(n+10,i));
	for(i=0;i<10;i++)vc.pb(mkp(n+11,bt[i]));
	InitG(n+12,(int)vc.size());
	for(i=0;i<(int)vc.size();i++)MakeG(i,vc[i].fr,vc[i].sc);
}
/*int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	
	return 0;
}*/

Bob

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include "Boblib.h"
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=2e3+50;
const ll mod=1e9+7;
using namespace std;
int i,j,sa,sb,y,x,pr,nx,v[nmax],rs[nmax],bt[nmax];
vector<int>g[nmax];
vector<pair<int,int> >vc;
pair<int,int>mx;
void Bob(int n,int m,int a[],int b[])
{
	for(i=0;i<m;i++)
	{
		g[a[i]].pb(b[i]);
		g[b[i]].pb(a[i]);
	}
	for(i=0;i<n;i++)mx=max(mx,mkp((int)g[i].size(),i));
	sa=mx.sc;
	v[sa]=1;
	for(i=0;i<(int)g[sa].size();i++)v[g[sa][i]]=1;
	for(i=0;i<n;i++)if(!v[i])sb=i;
	for(i=0;i<n;i++)v[i]=0;
	v[sa]=v[sb]=1;
	mx=mkp(0,0);
	for(i=0;i<(int)g[sb].size();i++)
	{
		x=g[sb][i];
		v[x]=1;
		bt[x]=1;
	}
	for(i=0;i<(int)g[sb].size();i++)
	{
		x=g[sb][i],y=0;
		for(j=0;j<(int)g[x].size();j++)y+=bt[g[x][j]];
		if(y==1)mx=max(mx,mkp((int)g[x].size(),x));
	}
	x=mx.sc,pr=inf;
	for(i=0;i<10;i++)
	{
		for(j=0;j<(int)g[x].size();j++)
		{
			y=g[x][j];
			if(v[y])
			{
				if(y!=sa && y!=sb && y!=pr)nx=y;
				continue;
			}
			rs[y]|=(1<<i);
		}
		pr=x;
		x=nx;
	}
	for(i=0;i<n;i++)
	{
		if(v[i])continue;
		for(j=0;j<(int)g[i].size();j++)
		{
			x=g[i][j];
			if(v[x])continue;
			x=rs[x];
			if(x>rs[i])vc.pb(mkp(rs[i],x));
		}
	}
	InitMap(n-12,(int)vc.size());
	for(i=0;i<(int)vc.size();i++)MakeMap(vc[i].fr,vc[i].sc);
}
/*int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	
	return 0;
}*/

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