답안 #407074

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
407074	2021-05-18T12:45:43 Z	79brue	항공 노선도 (JOI18_airline)	C++14	컴파일중	867 ms	33580 KB

Alice

#include "Alicelib.h"
#include <bits/stdc++.h>

using namespace std;

namespace AliceLib{
    int n, m;
    int renum[1002];
    vector<int> link[1002];
    vector<pair<int, int> > resultingGraph;

    int counter[10];
    int oneHand;

    void Alice(int N, int M, int A[], int B[]){
        n = N, m = M;
        for(int i=0; i<m; i++){
            link[A[i]].push_back(B[i]);
            link[B[i]].push_back(A[i]);

            resultingGraph.push_back(make_pair(A[i], B[i]));
        }

        for(int i=0; i<n; i++) for(int j=0; j<10; j++){
            if((i>>j)&1) counter[j]++;
        }
        for(int i=0; i<10; i++) if(counter[i] != 8) oneHand = i;

        int rpnt = 0;
        for(int i=0; i<n; i++){
            while(__builtin_popcount(rpnt) >= 9) rpnt++;
            renum[i] = rpnt++;
        }

        /// Edge type A: 0 - 1 - ... - 9
        for(int i=0; i<10; i++) if((i+1)%10 != oneHand) resultingGraph.push_back(make_pair(n+i, n+(i+1)%10));

        /// Edge type B: Every other vertexes - (n+10)
        for(int i=0; i<n+10; i++){
            if(i!=n+oneHand) resultingGraph.push_back(make_pair(i, n+10));
        }

        /// Edge type C: n~n+9 - n+11
        for(int i=n; i<n+10; i++) resultingGraph.push_back(make_pair(i, n+11));

        /// Edge type D: 0~n-1 - n~n+9
        for(int i=0; i<n; i++){
            for(int j=0; j<10; j++){
                if((renum[i]>>j)&1) resultingGraph.push_back(make_pair(i, n+j));
            }
        }

        InitG(n+12, (int)resultingGraph.size());
        int edgeCnt = 0;
        for(auto p: resultingGraph){
            MakeG(edgeCnt++, p.first, p.second);
        }
    }
}

void Alice(int N, int M, int A[], int B[]){
    AliceLib::Alice(N, M, A, B);
}

Bob

#include <bits/stdc++.h>
#include "Boblib.h"

using namespace std;

namespace BobLib{
    int n, m;
    vector<int> link[1022];
    int deg[1022];
    int number[1022];
    int loc[1022];

    bool candidate[1022];

    int renum[1022];
    vector<pair<int, int> > edges;

    int counter[10];
    int oneHand;

    void Bob(int N, int M, int A[], int B[]){
        n = N - 12, m = M;
        for(int i=0; i<m; i++){
            link[A[i]].push_back(B[i]);
            link[B[i]].push_back(A[i]);
            deg[A[i]]++, deg[B[i]]++;
        }

        int rpnt = 0;
        for(int i=0; i<n; i++){
            while(__builtin_popcount(rpnt) >= 9) rpnt++;
            renum[rpnt++] = i;
        }

        for(int i=0; i<n; i++) for(int j=0; j<10; j++){
            if((i>>j)&1) counter[j]++;
        }
        for(int i=0; i<10; i++) if(counter[i] != 8) oneHand = i;

        for(int i=0; i<n+12; i++){
            if(deg[i] == n+9){
                loc[n+10] = i, number[i] = n+10;

                set<int> st;
                for(int j=0; j<n+12; j++) if(j!=i) st.insert(j);
                for(auto y: link[i]) st.erase(y);

                int pnt = *st.begin();
                if(deg[pnt] != 10) pnt = *st.rbegin();
                loc[n+11] = pnt, number[pnt] = n;

                pnt = *st.begin() + *st.rbegin() - pnt;
                loc[n+oneHand] = pnt, number[pnt] = n+oneHand;
            }
        }

        for(auto nxt: link[loc[n+11]]) candidate[nxt] = 1;
        int pnt = loc[n+oneHand];
        for(int i=n+(oneHand+1)%10; i != n+oneHand; i = (i==n+9 ? n : i+1)){
            for(auto nxt: link[pnt]){
                if(number[nxt] || !candidate[nxt]) continue;
                pnt = nxt;
                loc[i] = pnt, number[pnt] = i;
                break;
            }
        }

        for(int i=0; i<n+12; i++){
            if(number[i] >= n) continue;
            for(auto j: link[i]){
                if(number[j] < n || number[j] == n+10) continue;
                number[i] += 1 << (number[j] - n);
            }
            number[i] = renum[number[i]];
        }

        for(int i=0; i<n+12; i++){
            if(number[i] >= n) continue;
            for(auto j: link[i]){
                if(number[j] >= n || number[j] > number[i]) continue;
                edges.emplace_back(number[i], number[j]);
            }
        }

        InitMap(n, (int)edges.size());
        for(auto p: edges){
            MakeMap(p.first, p.second);
        }
    }
}

void Bob(int N, int M, int A[], int B[]){
    BobLib::Bob(N, M, A, B);
}