oj.uz

Submission #260366

# Submission time Handle Problem Language Result Execution time Memory
260366 2020-08-10T07:17:41 Z 반딧불(#5056) Airline Route Map (JOI18_airline) C++14
0 / 100
 817 ms 39264 KB 
#include <bits/stdc++.h>
#include "Alicelib.h"

using namespace std;

typedef long long ll;

namespace AA{
    vector<int> link[1020];
    vector<pair<int, int> > edge;
}
using namespace AA;

void Alice(int N, int M, int A[], int B[]){
    for(int i=0; i<M; i++){ /// original graph
        link[A[i]].push_back(B[i]);
        link[B[i]].push_back(A[i]);
    }
    for(int i=0; i<N; i++){ /// vertex X
        link[N+11].push_back(i);
        link[i].push_back(N+11);
    }
    for(int d=0; d<10; d++){ /// vertex d0, d1, ..., d9
        for(int i=0; i<N; i++){
            if(i & (1<<d)) link[i].push_back(N+d), link[N+d].push_back(i);
        }
    }

    for(int d=0; d<=5; d++){
        for(int e=9; d+e>=10 && e>d; e--){
            link[N+d].push_back(N+e);
            link[N+e].push_back(N+d);
        }
    }

    for(int d=5; d<=9; d++){
        link[N+10].push_back(N+d);
        link[N+d].push_back(N+10);
    }

    for(int i=0; i<N+12; i++){
        for(auto &j: link[i]){
            if(i < j) edge.push_back(make_pair(i, j));
        }
    }

    InitG(N+12, (int)edge.size());
    int cnt = 0;
    for(auto &x: edge){
        MakeG(cnt++, x.first, x.second);
    }
}

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

using namespace std;

typedef long long ll;

namespace BB{
    int n, m;
    int idx[1020];
    vector<int> glink[1020];
    vector<int> link[1002];

    int vertexX, vertexY;
    int vertexD[10];
    vector<int> specialVertices;
    bool isSpecial[1020];
    int specialDegree[1020];

    vector<pair<int, int> > edge;
}
using namespace BB;

void Bob(int V, int U, int C[], int D[]){
    n = V-12;
    for(int i=0; i<U; i++){
        glink[C[i]].push_back(D[i]);
        glink[D[i]].push_back(C[i]);
    }

    for(int i=0; i<V; i++){
        if(glink[i].size() == n){
            vertexX = i;

            for(int j=0; j<V; j++) isSpecial[j] = 1;
            isSpecial[i] = 0;
            for(auto &x: glink[i]) isSpecial[x] = 0;

            for(int j=0; j<V; j++){
                if(isSpecial[j]) specialVertices.push_back(j);
            }
            break;
        }
    }

    for(auto &x: specialVertices){
        for(auto &y: glink[x]){
            if(isSpecial[y]) specialDegree[x]++;
        }

        if(specialDegree[x] != 5){
            vertexD[specialDegree[x]] = x;
        }
        else{
            if(specialDegree[x] == glink[x].size()) vertexY = x;
            else vertexD[5] = x;
        }
    }

    for(int i=0; i<V; i++){
        if(isSpecial[i] || i == vertexX) continue;

        for(auto &x: glink[i]){
            if(isSpecial[x]) idx[i] += 1 << specialDegree[x];
        }
    }

    for(int i=0; i<V; i++){
        if(isSpecial[i] || i == vertexX) continue;

        for(auto &x: glink[i]){
            if(!isSpecial[x] && x != vertexX){
                link[idx[i]].push_back(idx[x]);
            }
        }
    }

    for(int i=0; i<n; i++){
        for(auto &x: link[i]){
            if(i < x){
                edge.push_back(make_pair(i, x));
            }
        }
    }

    InitMap(n, (int)edge.size());
    for(auto &x: edge){
        MakeMap(x.first, x.second);
    }
}

Compilation message

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:32:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(glink[i].size() == n){
            ~~~~~~~~~~~~~~~~^~~~
Bob.cpp:55:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(specialDegree[x] == glink[x].size()) vertexY = x;
                ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6912 KB Output is correct
2 Correct 5 ms 6912 KB Output is correct
3 Correct 5 ms 6912 KB Output is correct
4 Correct 5 ms 6912 KB Output is correct
5 Correct 6 ms 6912 KB Output is correct
6 Correct 5 ms 6912 KB Output is correct
7 Correct 5 ms 6912 KB Output is correct
8 Incorrect 5 ms 6912 KB Wrong Answer [11]
9 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6912 KB Output is correct
2 Correct 5 ms 6912 KB Output is correct
3 Correct 5 ms 6912 KB Output is correct
4 Correct 5 ms 6912 KB Output is correct
5 Correct 6 ms 6912 KB Output is correct
6 Correct 5 ms 6912 KB Output is correct
7 Correct 5 ms 6912 KB Output is correct
8 Incorrect 5 ms 6912 KB Wrong Answer [11]
9 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Incorrect 817 ms 39264 KB Wrong Answer [11]
2 Halted 0 ms 0 KB -