Submission #1213339

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213339		boss_zz	항공 노선도 (JOI18_airline)	C++20	100 / 100	180 ms	27052 KiB

Alice

#include "Alicelib.h"
#include<bits/stdc++.h>
#define rep(a,b,c) for(ll a=b;a<=c;++a) 
#define ll long long 
#define ff first 
#define ss second 
#define mp make_pair 
using namespace std;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
static const ll N=1005,inf=1e18;
static int n,m;
static vector<pii> edge;
void Alice( int NN, int MM, int A[], int B[] ){
	n=NN,m=MM;
    rep(i,0,n+9) edge.push_back(mp(n+11,i));
    rep(i,n,n+9) edge.push_back(mp(n+10,i));
    rep(i,n,n+8) edge.push_back(mp(i,i+1));
    rep(i,0,m-1) edge.push_back(mp(A[i],B[i]));
    rep(i,0,n-1) rep(j,0,9) if((i>>j)&1LL) edge.push_back(mp(i,n+j));
    InitG(n+12,(int)edge.size());
    rep(i,0,(int)edge.size()-1) MakeG(i,edge[i].ff,edge[i].ss);
}

Bob

#include "Boblib.h"
#include<bits/stdc++.h>
#define rep(a,b,c) for(ll a=b;a<=c;++a) 
#define ll long long 
#define ff first 
#define ss second 
#define mp make_pair 
using namespace std;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
static const ll N=1025,inf=1e18;
static int n,m,deg[N],G[N][N],X[15],F[N];
static vector<pii> edge;
static vector<int> adj[N],SP;
static bitset<N> used,ex,head;
static void build(){
    rep(i,0,n-1) if(deg[i]==n-2){
        rep(j,0,n-1) if(j!=i&&!G[i][j]){
            for(int x:adj[j]) SP.push_back(x),ex[x]=1;
            for(int x:adj[j]){
                for(int v:adj[x]){
                    if(ex[v]){
                        head[x]=!head[x];
                    }
                }
            }
            ex[i]=ex[j]=1;
        }
    }
    assert(!SP.empty());
    sort(SP.begin(),SP.end(),[](int a,int b){
        if(head[a]==head[b]) return deg[a]>deg[b];
        return head[a]>head[b];
    });
    X[0]=SP.front();used[X[0]]=1;
    queue<int> Q;
    Q.push(X[0]);
    int cnt=0;
    while(!Q.empty()){
        ll u=Q.front();
        Q.pop();
        rep(i,0,(int)SP.size()-1) if(!used[SP[i]]){
            if(G[u][SP[i]]){
                Q.push(SP[i]);
                used[SP[i]]=1;
                X[++cnt]=SP[i];
                break;
            }
        }
    }
}
void Bob( int V, int U, int C[], int D[] ){
    n=V;m=U;
    rep(i,0,m-1){
        adj[C[i]].push_back(D[i]);
        adj[D[i]].push_back(C[i]);
        G[C[i]][D[i]]=G[D[i]][C[i]]=1;
    }
    rep(i,0,n-1) deg[i]=(int)adj[i].size();
    build();
    rep(i,0,n-1){
        if(ex[i]) continue;
        rep(j,0,9){
            if(G[i][X[j]]){
                F[i]+=(1LL<<j);
            }
        }
    }
    rep(i,0,m-1) if(!ex[C[i]]&&!ex[D[i]]) edge.push_back(mp(F[C[i]],F[D[i]]));
    InitMap(V-12,(int)edge.size());
    for(auto o:edge) MakeMap(o.ff,o.ss);
}

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