Submission #1146915

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146915		guagua0407	Airline Route Map (JOI18_airline)	C++20	100 / 100	175 ms	23256 KiB

Alice

#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

void Alice( int n, int M, int A[], int B[] ){
    vector<pair<int,int>> e;
    for(int i=0;i<M;i++){
        e.push_back({A[i],B[i]});
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<10;j++){
            if((i+1)&(1<<j)){
                e.push_back({i,n+j});
            }
        }
    }
    for(int i=0;i<n;i++){
        e.push_back({n+10,i});
    }
    for(int i=n;i<n+10-1;i++){
        e.push_back({i,i+1});
    }
    e.push_back({n+11,n+10});
    int m=(int)e.size();
	InitG( n+12,m );
    for(int i=0;i<m;i++){
        MakeG(i,e[i].f,e[i].s);
    }
}

Bob

#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

void Bob( int V, int U, int C[], int D[] ){
    vector<int> deg(V);
    vector<vector<int>> adj(V);
    for(int i=0;i<U;i++){
        deg[C[i]]++;
        deg[D[i]]++;
        adj[C[i]].push_back(D[i]);
        adj[D[i]].push_back(C[i]);
    }
    vector<int> to(V);
    vector<int> rev(V,-1);
    vector<bool> used(V);
    int n=V-12;
    for(int i=0;i<V;i++){
        if(deg[i]==1 and deg[adj[i][0]]==n+1){
            to[n+11]=i;
            to[n+10]=adj[i][0];
            rev[i]=n+11;
            rev[adj[i][0]]=n+10;
            used[i]=true;
            used[adj[i][0]]=true;
            break;
        }
    }
    for(auto v:adj[to[n+10]]){
        used[v]=true;
    }
    int node=-1;
    for(int i=0;i<V;i++){
        if(used[i]) continue;
        if(node==-1){
            node=i;
        }
    }
    vector<bool> used2(V);
    int a=node,b=node;
    while(true){
        used2[a]=true;
        int tmp=-1;
        for(auto v:adj[a]){
            if(used[v] or used2[v]) continue;
            tmp=v;
            break;
        }
        if(tmp==-1) break;
        a=tmp;
    }
    while(true){
        used2[b]=true;
        int tmp=-1;
        for(auto v:adj[b]){
            if(used[v] or used2[v]) continue;
            tmp=v;
            break;
        }
        if(tmp==-1) break;
        b=tmp;
    }
    int en=(deg[a]>deg[b]?b:a);
    int cur=n+9;
    while(en!=-1){
        used[en]=true;
        to[cur]=en;
        rev[en]=cur;
        cur--;
        int tmp=-1;
        for(auto v:adj[en]){
            if(used[v]) continue;
            tmp=v;
        }
        en=tmp;
    }
    vector<pair<int,int>> e;
    for(int i=0;i<V;i++){
        if(rev[i]!=-1) continue;
        rev[i]=0;
        for(auto v:adj[i]){
            if(n<=rev[v] and rev[v]<n+10){
                rev[i]+=(1<<(rev[v]-n));
            }
        }
        rev[i]--;
        for(auto v:adj[i]){
            if(0<=rev[v] and rev[v]<n){
                e.push_back({rev[i],rev[v]});
            }
        }
    }
    int m=(int)e.size();
	InitMap( n, m );
	for(auto v:e){
        MakeMap(v.f,v.s);
	}
}
/*
4 3
0 1
0 2
0 3
*/

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