Submission #1147144

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147144		fatman87878	항공 노선도 (JOI18_airline)	C++20	0 / 100	160 ms	19208 KiB

Alice

#include "Alicelib.h"
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define all(x) (x).begin(),(x).end()
#define ll long long

constexpr int maxN=2e5+5;

void Alice( int N, int M, int A[], int B[] ){
    vector<pair<int,int>> edges;
    for(int i = 0;i<M;i++)edges.emplace_back(A[i],B[i]);
    for(int i = 0;i<10;i++){
        if(i)edges.emplace_back(N+i,N+i+1);
        edges.emplace_back(N,N+i+1);
        for(int j = 0;j<N;j++)if((j+1)>>i&1)edges.emplace_back(N+i+1,j);
    }
    for(int i = 0;i<N+11;i++)if(i!=N)edges.emplace_back(N+11,i);
    InitG(N+12,edges.size());
    int cnt = 0;
    for(auto [a,b]:edges)MakeG(cnt++,a,b);
}

Bob

#include "Boblib.h"
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define all(x) (x).begin(),(x).end()
#define ll long long

constexpr int maxN=2e5+5;

void Bob( int V, int U, int C[], int D[] ){
    vector<int> deg(V,0);
    vector adj(V,vector(V,0));
    for(int i = 0;i<U;i++)deg[C[i]]++,deg[D[i]]++,adj[C[i]][D[i]]=adj[D[i]][C[i]]=1;
    int idx = max_element(all(deg))-deg.begin(),idx2 = 0;
    vector<int> bits,dead(V,0);
    dead[idx] = 1;
    for(int i = 0;i<V;i++)if(i!=idx&&!adj[idx][i])idx2=i;
    dead[idx2] = 1;
    for(int i = 0;i<V;i++)if(adj[idx2][i])bits.emplace_back(i),dead[i]=1;
    vector<int> neighbor[10];
    for(int i = 0;i<10;i++){
        int b1 = bits[i];
        for(int j = 0;j<10;j++){
            int b2 = bits[j];
            if(b2!=b1&&adj[b1][b2])neighbor[i].emplace_back(j);
        }
    }
    int ends[2]{};
    for(int i = 0;i<10;i++)if(neighbor[i].size()==1){
        if(!ends[0])ends[0]=i;
        else {
            ends[1] = i;
            if(deg[bits[ends[0]]]<deg[bits[ends[1]]])swap(ends[0],ends[1]);
        }
    }
    vector<int> rlid(V,0),vis(10,0);
    for(int pos = ends[0],bit = 0;;bit++){
        vis[pos] = 1;
        for(int i = 0;i<V;i++)if(!dead[i]&&adj[bits[pos]][i]){
            rlid[i]|=1<<bit;
        }
        if(pos==ends[1])break;
        if(vis[neighbor[pos][0]])pos = neighbor[pos][1];
        else pos = neighbor[pos][0];
    }
    vector<pair<int,int>> edges;
    for(int i = 0;i<U;i++){
        if(!dead[C[i]]&&!dead[D[i]])edges.emplace_back(rlid[C[i]]-1,rlid[D[i]]-1);
    }
    InitMap(V-12,edges.size());
    for(auto [a,b]:edges)MakeMap(a,b);
}

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