Submission #407106

#	Time	Username	Problem	Language	Result	Execution time	Memory
407106		79brue	Airline Route Map (JOI18_airline)	C++14	100 / 100	839 ms	33732 KiB

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;

    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]));
        }

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

        /// Edge type A: 0 - 1, 0 - 2 - 3, 0 - 4 - 5 - 6 - 7 - 8 - 9
        vector<int> tPar = {0, 0, 0, 2, 0, 4, 5, 6, 7, 8};
        for(int i=1; i<10; i++) resultingGraph.push_back(make_pair(n+i, n+tPar[i]));

        /// Edge type B: Every other vertexes - (n+10)
        for(int i=0; i<n+10; i++){
            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], tdeg[1022];
    int number[1022];
    int loc[1022];

    bool candidate[1022];

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

    int tdfs(int x, int par = -1, int depth = 0){
        int ret = 0;
        for(auto y: link[x]){
            if(y == par || !candidate[y]) continue;
            ret = tdfs(y, x, depth+1)+1;
        }
        if(depth){
            int result;
            if(depth + ret == 1) result = depth;
            else if(depth + ret == 2) result = depth + 1;
            else result = depth + 3;

            loc[n+result] = x, number[x] = n+result;
        }
        return ret;
    }

    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+12; i++){
            if(deg[i] == n+10){
                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();
                loc[n+11] = pnt, number[pnt] = n+11;
            }
        }

        for(auto nxt: link[loc[n+11]]) candidate[nxt] = 1;
        for(int i=0; i<n+12; i++){
            for(auto j: link[i]){
                if(candidate[i] && candidate[j]) tdeg[i]++;
            }
        }

        for(int i=0; i<n+12; i++){
            if(tdeg[i] == 3){
                loc[n] = i, number[i] = n;
                break;
            }
        }

        tdfs(loc[n]);

        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);
}

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