Submission #943860

#	Time	Username	Problem	Language	Result	Execution time	Memory
943860		beepbeepsheep	Airline Route Map (JOI18_airline)	C++17	100 / 100	531 ms	47708 KiB

Alice

#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#define ll long long
#include <bits/stdc++.h>
using namespace std;
static vector<ll> adj[1012];
void Alice( int N, int M, int A[], int B[] ){
    if (N==1){
        InitG(1,0);
        return;
    }
    ll cnt=0;
    for (int i=0;i<M;i++){
        adj[A[i]].emplace_back(B[i]);
        cnt++;
    }
    for (int i=0;i<N;i++){
        for (int j=0;j<10;j++){
            if (i & (1<<j)){
                adj[N+j].emplace_back(i);
                cnt++;
            }
        }
    }
    cnt+=N+10+10+9;
    InitG(N+12,cnt);
    for (int i=0;i<N+10;i++){
        --cnt;
        MakeG(cnt,i,N+10);
    }
    for (int i=N;i<N+10;i++){
        --cnt;
        MakeG(cnt,i,N+11);
    }
    for (int i=N;i<N+9;i++){
        --cnt;
        MakeG(cnt,i,i+1);
    }
    for (int i=0;i<1012;i++){
        for (auto u:adj[i]){
            --cnt;
            MakeG(cnt,i,u);
        }
    }
}

Bob

#include "Boblib.h"
#include <cassert>
#include <cstdio>
#define ll long long
#include <bits/stdc++.h>
using namespace std;
vector<ll> bits;
static ll adj[1012][1012];
ll deg[1012];
ll bitsDeg[1012];
ll vis[1012];
ll idx[1012];
map<ll,ll> m;
vector<ll> out[1012];
void Bob( int V, int U, int C[], int D[] ){
    if (V==1){
        InitMap(1,0);
        return;
    }
    for (int i=0;i<U;i++){
        adj[C[i]][D[i]]=true;
        adj[D[i]][C[i]]=true;
        deg[C[i]]++,deg[D[i]]++;
    }
    ll md=0;
    for (int i=1;i<V;i++){
        if (deg[i]>deg[md]) md=i;
    }
    ll hub=0;
    for (int i=0;i<V;i++){
        if (md==i) continue;
        if (adj[md][i]==0){
            hub=i;
            break;
        }
    }
    for (int i=0;i<V;i++){
        if (adj[hub][i]) bits.emplace_back(i);
    }
    for (int i=0;i<10;i++){
        for (int j=i+1;j<10;j++){
            if (adj[bits[i]][bits[j]]){
                bitsDeg[bits[i]]++;
                bitsDeg[bits[j]]++;
            }
        }
    }
    ll s=-1,e=-1;
    for (int i=0;i<V;i++){
        if (bitsDeg[i]==1 && s==-1) s=i;
        else if (bitsDeg[i]==1) e=i;
    } //find the start and ends of the chains
    if (deg[s]<deg[e]) swap(s,e);
    //start at 2^0 to 2^9
    ll ptr=s,cnt=0;
    m[s]=0,m[e]=9;
    vis[s]=true;
    while (ptr!=e){
        for (int i=0;i<V;i++){
            if (i==ptr) continue;
            if (bitsDeg[i] && !vis[i] && adj[ptr][i]){
                //if is special node and not visited before
                //and is adjacents
                ptr=i;
                break;
            }
        }
        cnt++;
        m[ptr]=cnt;
        vis[ptr]=true;
    }
    vis[e]=true;
    vis[hub]=true;
    vis[md]=true;
    for (int i=0;i<V;i++){
        if (vis[i]) continue;
        if (i==hub || i==md) continue;
        //special node
        for (int j=0;j<V;j++){
            if (i==j) continue;
            if (j==hub || j==md) continue;
            //same guy
            if (adj[i][j]==0) continue;
            //no edge
            if (vis[j]==0) continue;
            //is not a special node
            idx[i]+=(1<<m[j]);
        }
    }
    ll ed=0;
    for (int i=0;i<U;i++){
        if (vis[C[i]] ||vis[D[i]]) continue;
        out[idx[C[i]]].emplace_back(idx[D[i]]);
        ed++;
    }
    InitMap(V-12,ed);
    for (int i=0;i<1012;i++){
        for (auto u:out[i]){
            MakeMap(i,u);
        }
    }
}

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