Submission #107605

#	Time	Username	Problem	Language	Result	Execution time	Memory
107605		SYCstudio	Airline Route Map (JOI18_airline)	C++14	100 / 100	866 ms	31560 KiB

Alice

#include "Alicelib.h"
#include<cstdio>
#include<vector>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;

#define pb push_back
#define mp make_pair
#define ft first
#define sd second
static const int maxN=1024;
static const int BIT=10;//warning
static vector<pair<int,int> > E;

void Alice(int N,int M,int A[],int B[]){
    //cout<<"N:"<<N<<" "<<M<<endl;
    for (int i=0;i<M;i++) E.pb(mp(A[i],B[i]));
    for (int i=0;i<N;i++){
	E.pb(mp(i,N+BIT));
	for (int j=0;j<BIT;j++)
	    if (i&(1<<j)) E.pb(mp(i,N+j));
    }
    for (int i=1;i<BIT;i++) E.pb(mp(N+i-1,N+i));
    for (int i=2;i+1<BIT;i++) E.pb(mp(N,N+i));
    for (int i=0;i<BIT;i++) E.pb(mp(N+i,N+BIT)),E.pb(mp(N+i,N+BIT+1));

    //for (int i=0;i<E.size();i++) cout<<E[i].ft<<" "<<E[i].sd<<endl;

    InitG(N+BIT+2,(int)(E.size()));
    for (int i=0,sz=E.size();i<sz;i++) MakeG(i,E[i].ft,E[i].sd);
    return;
}

Bob

#include "Boblib.h"
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;

#define mp make_pair
#define ft first
#define sd second
static const int maxN=1020;
static const int BIT=10;//warning!

static vector<int> E[maxN];
static int Mark[maxN],Id[maxN],scnt,BS[BIT+10];

static bool cmps(int a,int b);
void Bob(int V,int U,int C[],int D[]){
    for (int i=0;i<U;i++) E[C[i]].push_back(D[i]),E[D[i]].push_back(C[i]);
    //cout<<"BOB:"<<endl;
    //for (int i=0;i<U;i++) cout<<C[i]<<" "<<D[i]<<endl;
    //for (int i=0;i<V;i++) cout<<E[i].size()<<" ";cout<<endl;
    int mrt=0;for (int i=0;i<V;i++) if (E[i].size()>E[mrt].size()) mrt=i;
    Mark[mrt]=-1;
    for (int i=0,sz=E[mrt].size();i<sz;i++) Mark[E[mrt][i]]=1;
    int id12=0;while (Mark[id12]) ++id12;

    pair<int,int> Seq[BIT+10];
    for (int i=0,sz=E[id12].size();i<sz;i++) Mark[E[id12][i]]=2,Seq[scnt++]=mp(0,E[id12][i]);
    for (int i=0;i<BIT;i++){
	int u=Seq[i].sd;
	for (int j=0,sz=E[u].size();j<sz;j++) if (Mark[E[u][j]]==2) ++Seq[i].ft;
    }
    //for (int i=0;i<BIT;i++) cout<<"("<<Seq[i].sd<<" "<<Seq[i].ft<<")";cout<<endl;
    //cout<<"scnt:"<<scnt<<endl;
    int bitone=0;
    for (int i=1;i<BIT;i++) if (Seq[i].ft>Seq[bitone].ft) bitone=i;
    bitone=Seq[bitone].sd;
    for (int i=0,u=bitone,sz=E[u].size();i<sz;i++) if (Mark[E[u][i]]==2) Mark[E[u][i]]=3;

    BS[BIT]=-1;
    for (int i=0;i<BIT;i++) if (Mark[Seq[i].sd]==2&&Seq[i].sd!=bitone) BS[BIT-1]=Seq[i].sd;
    for (int i=BIT-1;i>=2;i--){
	int u=BS[i];
	for (int j=0,sz=E[u].size();j<sz;j++){
	    int v=E[u][j];
	    if (Mark[v]==3&&v!=bitone&&v!=BS[i+1]){
		BS[i-1]=v;break;
	    }
	}
    }
    BS[0]=bitone;
    //cout<<"BS:";for (int i=0;i<BIT;i++) cout<<BS[i]<<" ";cout<<endl;

    for (int i=0;i<BIT;i++){
	int u=BS[i];
	for (int j=0,sz=E[u].size();j<sz;j++) if (Mark[E[u][j]]==1) Id[E[u][j]]|=(1<<i);
    }

    int mcnt=0;for (int i=0;i<U;i++) if (Mark[C[i]]==1&&Mark[D[i]]==1) ++mcnt;
    //cout<<"mcnt:"<<mcnt<<endl;
    //for (int i=0;i<V;i++) cout<<Id[i]<<" ";cout<<endl;
    InitMap(V-BIT-2,mcnt);
    for (int i=0;i<U;i++) if (Mark[C[i]]==1&&Mark[D[i]]==1) MakeMap(Id[C[i]],Id[D[i]]);
    
    return;
}

Compilation message (stderr)

Bob.cpp:19:13: warning: 'bool cmps(int, int)' declared 'static' but never defined [-Wunused-function]
 static bool cmps(int a,int b);
             ^~~~

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