oj.uz

답안 #407105

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
407105 2021-05-18T13:26:44 Z 79brue 항공 노선도 (JOI18_airline) C++14
0 / 100
 637 ms 33488 KB 
#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, 3, 4, 5, 6, 7};
        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);
}


#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
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4716 KB Wrong Answer [11]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4716 KB Wrong Answer [11]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 637 ms 33488 KB Wrong Answer [11]
2 Halted 0 ms 0 KB -