Submission #114842

#	Time	Username	Problem	Language	Result	Execution time	Memory
114842		shayan_p	Airline Route Map (JOI18_airline)	C++14	100 / 100	780 ms	25672 KiB

Alice

// High above the clouds there is a rainbow...

#include<bits/stdc++.h>

#include "Alicelib.h"

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn=1111,lg=10;

static vector<pii>v;

void Alice(int n,int m,int a[],int b[]){
    for(int i=0;i<n;i++){
	for(int j=0;j<lg;j++){
	    if(bit(i+1,j)) v.PB({i,j+n});
	}
    }
    for(int i=0;i<n+lg;i++){
	v.PB({n+lg,i});
    }
    for(int i=n;i<n+lg;i++){
	v.PB({n+lg+1,i});
    }
    for(int i=n;i<n+lg-1;i++){
	v.PB({i,i+1});
    }
    InitG(n+lg+2,m+sz(v));
    //  cout<<n+lg+2<<" "<<m+sz(v)<<endl;
    for(int i=0;i<m;i++){
	//	cout<<a[i]<<" "<<b[i]<<endl;
	MakeG(i,a[i],b[i]);
    }
    for(int i=0;i<sz(v);i++){
	//	cout<<v[i].F<<" "<<v[i].S<<endl;
	MakeG(i+m,v[i].F,v[i].S);
    }
}
/*
int a[maxn],b[maxn];

int main(){
    int n,m;cin>>n>>m;
    for(int i=0;i<m;i++){
	cin>>a[i]>>b[i];
    }
    Alice(n,m,a,b);
}
*/

Bob

// High above the clouds there is a rainbow...

#include<bits/stdc++.h>

#include "Boblib.h"

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn=1111,lg=10;

static bool bad[maxn];
static int lab[maxn];

static vector<int>v[maxn];
static vector<pii>ans;
static int w2;

static void solve(int u,int prev=-1,int bt=0){
    int nxt=-1;
    for(int y:v[u]){
	if(y==w2) continue;
	if(y==prev) continue;
	if(bad[y])
	    lab[y]+= (1<<bt);
	else
	    nxt=y;
    }
    if(nxt!=-1) solve(nxt,u,bt+1);
}

void Bob(int n,int m,int a[],int b[]){
    for(int i=0;i<m;i++)
	v[a[i]].PB(b[i]), v[b[i]].PB(a[i]);
    int w=0;
    for(int i=0;i<n;i++){
	if(sz(v[i])>sz(v[w])) w=i;
    }
    bad[w]=1;
    for(int y:v[w]){
	bad[y]=1;
    }
    w2=-1;
    for(int i=0;i<n;i++){
	if(!bad[i]) w2=i;
    }
    bad[w2]=1;
    for(int y:v[w2]){
	bad[y]=0;
    }

    int A=-1;
    
    for(int i=0;i<n;i++){
	if(bad[i]) continue;
	int C=0;
	for(int y:v[i])
	    C+= !bad[y];
	if(C==1){
	    if(A==-1) A=i;
	    else if(sz(v[A]) < sz(v[i])) A=i;
	}
    }
    solve(A);

    lab[w]=0;
    
    int N=0,M=0;
    for(int i=0;i<m;i++){
	if(lab[a[i]]!=0 && lab[b[i]]!=0)
	    ans.PB( { lab[a[i]]-1, lab[b[i]]-1 } ),M++;
    }
    for(int i=0;i<n;i++){
	if(lab[i]!=0)
	    N++;
    }
    InitMap(N,M);
    for(pii p:ans){
	MakeMap(p.F,p.S);
    }
}
/*
int a[maxn],b[maxn];

int main(){
    int n,m;cin>>n>>m;
    for(int i=0;i<m;i++)
	cin>>a[i]>>b[i];
    Bob(n,m,a,b);
}

*/

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