Submission #260471

#	Time	Username	Problem	Language	Result	Execution time	Memory
260471		gs18115	Airline Route Map (JOI18_airline)	C++14	100 / 100	1002 ms	30920 KiB

Alice

#include"Alicelib.h"
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
const int siz=10;
void Alice(int N,int M,int A[],int B[])
{
    int n=N;
    int v=n+12;
    vector<pi>ed;
    for(int i=0;i<n;i++)
        for(int j=0;j<10;j++)
            if((i>>j&1)==0)
                ed.eb(i,n+j);
    for(int i=1;i<10;i++)
        ed.eb(n+i-1,n+i);
    for(int i=0;i<n;i++)
        ed.eb(i,n+10);
    ed.eb(n+10,n+11);
    for(int i=0;i<M;i++)
        ed.eb(A[i],B[i]);
    InitG(v,(int)ed.size());
    for(int i=0;i<(int)ed.size();i++)
        MakeG(i,ed[i].fi,ed[i].se);
    return;
}

Bob

#include"Boblib.h"
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
const int siz=10;
static vector<int>adj[1510];
static bool chk[1510],chk2[1510];
static int ind[1510];
static int coun[1510];
void Bob(int V,int U,int C[],int D[])
{
    int n=V-12;
    if(n==1)
        return InitMap(1,0);
    for(int i=0;i<U;i++)
        i[C][adj].eb(D[i]),i[D][adj].eb(C[i]);
    int nd=-1;
    for(int i=0;i<V;i++)
        if((int)adj[i].size()==1)
            chk[nd=i]=1;
    int nod=adj[nd][0];
    for(int&t:adj[nod])
        chk2[t]=1;
    chk[nod]=chk2[nod]=1;
    vector<int>bv;
    for(int i=0;i<V;i++)
        if(!chk2[i])
            bv.eb(i);
    int zero=-1;
    for(int&t:bv)
    {
        chk[t]=1;
        int cnt=0;
        for(int&r:adj[t])
            if(!chk2[r])
                cnt++;
        if(cnt==1)
            if(zero==-1||adj[t].size()<adj[zero].size())
                zero=t;
    }
    for(int i=0,prv=-1;i<10;i++)
    {
        coun[zero]=i;
        int nx=-1;
        for(int&t:adj[zero])
            if(!chk2[t]&&t!=prv)
                nx=t;
        prv=zero;
        zero=nx;
    }
    for(int i=0;i<V;ind[i++]^=1023)
        if(!chk[i])
            for(int&t:adj[i])
                if(!chk2[t])
                    ind[i]+=1<<coun[t];
    vector<pi>edg;
    for(int i=0;i<V;i++)
        if(!chk[i])
            for(int&t:adj[i])
                if(!chk[t]&&ind[i]<ind[t])
                    edg.eb(ind[i],ind[t]);
    InitMap(n,(int)edg.size());
    for(pi&t:edg)
        MakeMap(t.fi,t.se);
    return;
}

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