제출 #747664

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
747664		finn__	항공 노선도 (JOI18_airline)	C++17	100 / 100	654 ms	29344 KiB

Alice

#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;

void Alice(int N, int M, int A[], int B[])
{
    if (N == 1)
    {
        InitG(1, 0);
        return;
    }
    vector<pair<int, int>> edges;
    for (size_t i = 0; i < M; ++i)
        edges.emplace_back(A[i], B[i]);
    for (size_t i = 0; i < N; ++i)
        for (size_t j = 0; j < 10; ++j)
            if (i & (1 << j))
                edges.emplace_back(i, N + j);
    for (size_t i = 0; i < 10; ++i)
    {
        edges.emplace_back(N + i, N + 10);
        if (i < 9)
            edges.emplace_back(N + i, N + i + 1);
        if (i)
            edges.emplace_back(N + i, N + 11);
    }
    InitG(N + 12, edges.size());
    for (size_t i = 0; i < edges.size(); ++i)
        MakeG(i, edges[i].first, edges[i].second);
}

Bob

#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;

void Bob(int V, int U, int C[], int D[])
{
    if (V == 1)
    {
        InitMap(1, 0);
        return;
    }
    vector<vector<int>> G(V);
    for (size_t i = 0; i < U; ++i)
        G[C[i]].push_back(D[i]), G[D[i]].push_back(C[i]);

    int x = -1, y = -1;
    vector<int> d(V);
    for (size_t i = 0; i < V; ++i)
        if (G[i].size() == 10)
        {
            fill(d.begin(), d.end(), 0);
            int e[2] = {0, 0};
            bool possible = 1;
            for (auto const &j : G[i])
            {
                for (auto const &v : G[j])
                    if (find(G[i].begin(), G[i].end(), v) != G[i].end())
                        d[j]++;
                if (d[j] != 1 && d[j] != 2)
                {
                    possible = 0;
                    break;
                }
                e[d[j] - 1]++;
            }
            if (!possible || e[0] != 2 || e[1] != 8)
                continue;
            x = i;
            break;
        }
    vector<int> bit_vertices;
    for (size_t i = 0; i < V; ++i)
        if (G[i].size() == 9)
        {
            int v0 = -1;
            bool possible = 1;
            for (auto const &j : G[x])
                if (find(G[i].begin(), G[i].end(), j) == G[i].end())
                {
                    if (v0 != -1)
                        possible = 0;
                    v0 = j;
                }
            if (v0 == -1 || !possible || d[v0] != 1)
                continue;
            bit_vertices.clear();
            bit_vertices.push_back(v0);
            int last = -1;
            for (size_t k = 0; k < 9; ++k)
            {
                int v1 = -1;
                for (auto const &j : G[v0])
                    if (j != last && find(G[i].begin(), G[i].end(), j) != G[i].end())
                    {
                        if (v1 != -1)
                            possible = 0;
                        v1 = j;
                    }
                if (v1 == -1)
                {
                    possible = 0;
                    break;
                }
                last = v0;
                v0 = v1;
                bit_vertices.push_back(v0);
            }
            if (!possible || bit_vertices.size() != 10)
                continue;
            y = i;
            break;
        }

    vector<int> p(V);
    for (size_t i = 0; i < V; ++i)
        if (i != x && i != y && find(bit_vertices.begin(), bit_vertices.end(), i) == bit_vertices.end())
            for (auto const &v : G[i])
            {
                size_t const k = find(bit_vertices.begin(), bit_vertices.end(), v) - bit_vertices.begin();
                if (k != 10)
                    p[i] |= 1 << k;
            }
    vector<pair<int, int>> edges;
    for (size_t i = 0; i < V; ++i)
        if (i != x && i != y && find(bit_vertices.begin(), bit_vertices.end(), i) == bit_vertices.end())
            for (auto const &v : G[i])
                if (find(bit_vertices.begin(), bit_vertices.end(), v) == bit_vertices.end() && i < v)
                    edges.emplace_back(p[i], p[v]);
    InitMap(V - 12, edges.size());
    for (auto const &[u, v] : edges)
        MakeMap(u, v);
}

컴파일 시 표준 에러 (stderr) 메시지

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:13:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   13 |     for (size_t i = 0; i < M; ++i)
      |                        ~~^~~
Alice.cpp:15:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   15 |     for (size_t i = 0; i < N; ++i)
      |                        ~~^~~

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:13:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   13 |     for (size_t i = 0; i < U; ++i)
      |                        ~~^~~
Bob.cpp:18:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   18 |     for (size_t i = 0; i < V; ++i)
      |                        ~~^~~
Bob.cpp:42:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   42 |     for (size_t i = 0; i < V; ++i)
      |                        ~~^~~
Bob.cpp:85:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   85 |     for (size_t i = 0; i < V; ++i)
      |                        ~~^~~
Bob.cpp:86:15: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   86 |         if (i != x && i != y && find(bit_vertices.begin(), bit_vertices.end(), i) == bit_vertices.end())
      |             ~~^~~~
Bob.cpp:86:25: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   86 |         if (i != x && i != y && find(bit_vertices.begin(), bit_vertices.end(), i) == bit_vertices.end())
      |                       ~~^~~~
Bob.cpp:94:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   94 |     for (size_t i = 0; i < V; ++i)
      |                        ~~^~~
Bob.cpp:95:15: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   95 |         if (i != x && i != y && find(bit_vertices.begin(), bit_vertices.end(), i) == bit_vertices.end())
      |             ~~^~~~
Bob.cpp:95:25: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   95 |         if (i != x && i != y && find(bit_vertices.begin(), bit_vertices.end(), i) == bit_vertices.end())
      |                       ~~^~~~
Bob.cpp:97:98: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   97 |                 if (find(bit_vertices.begin(), bit_vertices.end(), v) == bit_vertices.end() && i < v)
      |                                                                                                ~~^~~

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