제출 #242815

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
242815		osaaateiasavtnl	항공 노선도 (JOI18_airline)	C++14	37 / 100	591 ms	11524 KiB

Alice

#include<bits/stdc++.h>
#include "Alicelib.h"
using namespace std;
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
void Alice( int N, int M, int A[], int B[] ){   
    vector <ii> ans;
    for (int i = 0; i < M; ++i)
        ans.app(mp(A[i], B[i]));
 
    // N ... N + 9 - bits
    for (int i = N; i < N + 9; ++i)
        ans.app(mp(i, i + 1));
        
    //N + 10 - connected with all except N + 11, N + 11 - only to bits
    for (int i = 0; i < N + 10; ++i) 
        if (i != N)
            ans.app(mp(i, N + 10));
    for (int i = N; i < N + 10; ++i)
        ans.app(mp(i, N + 11));
 
    for (int u = 0; u < N; ++u)
        for (int bit = 0; bit < 10; ++bit)
            if ((u >> bit) & 1)
                ans.app(mp(u, N+bit));
  
    vector <int> pw(N+12);
    for (auto e : ans) {
        ++pw[e.f];
        ++pw[e.s];
    }   

    for (int i = 0; i < N + 12; ++i) {
        if (i != N + 10 && pw[i] >= pw[N+10] && N > 2) {
            exit(1);
        }   
    }

    InitG(N + 12, ans.size());
    int ptr = 0;
    for (auto e : ans) {
        MakeG(ptr++, e.f, e.s);
    }
}
 

Bob

#include<bits/stdc++.h>
#include "Boblib.h"
using namespace std;
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
 
const int N = 2007;
bool g[N][N];
 
void Bob( int V, int E, int C[], int D[] ){
    int n = V - 12;

    /*
    if (n == 1) {
        InitMap(n, 0);
        return;
    }   
 
    if (n == 2) {
        if (E == 31) {
            InitMap(n, 0);
            return;
        }   
        else {
            InitMap(n, 1);
            MakeMap(0, 1);
            return;
        }   
    }
    */ 

    vector <int> pw(V);
    for (int i = 0; i < E; ++i) {
        ++pw[C[i]];
        ++pw[D[i]];
        g[C[i]][D[i]] = g[D[i]][C[i]] = 1;
    }
    
    vector <int> ord;
    for (int i = 0; i < V; ++i)
        ord.app(i);
    auto comp = [&](int u, int v) {
        return pw[u] < pw[v];
    };
    sort(all(ord), comp);
 
    auto checkmax = [&](int mx) {
        int sec = -1;
        for (int i = 0; i < V; ++i) {

            int pw = 0;
            for (int j = 0; j < V; ++j)
                pw += g[i][j];

            if (pw != 10)
                continue;

            if (i != mx && !g[i][mx]) {
                sec = i;
                break;
            }   
        }   
        return sec != -1;
    };  

    int ptr = V - 1;
    while (!checkmax(ord[ptr]))
        --ptr;
    int mx = ord[ptr];
 
    //cout << "mx " << mx << ' ' << pw[mx] << endl;
 
    int sec = -1;
    for (int i = 0; i < V; ++i) {

        int pw = 0;
        for (int j = 0; j < V; ++j)
            pw += g[i][j];

        if (pw != 10)
            continue;

        if (i != mx && !g[i][mx]) {
            sec = i;
            break;
        }   
    }   
 
    //cout << "sec " << sec << ' ' << pw[sec] << endl;
 
    vector <int> bit;
    for (int i = 0; i < V; ++i) {
        if (g[i][sec]) {
            bit.app(i);
        }   
    }   
    
    //cout << "bit " << bit.size() << endl;
 
    for (int i = 0; i < bit.size(); ++i) {
        if (!g[bit[i]][mx]) {
            swap(bit[0], bit[i]);
            //cout << "swap" << endl;
            break;
        }
    }   
 
    for (int i = 1; i < bit.size(); ++i) {
        int prv = bit[i-1];
        for (int j = i; j < bit.size(); ++j) {
            if (g[prv][bit[j]]) {
                swap(bit[i], bit[j]);
                break;
            }   
        }   
    }   
 
    vector <int> real;
    for (int i = 0; i < V; ++i) {
        if (!g[i][sec] && i != sec && i != mx)
            real.app(i);
    }   
 
    //cout << "real " << real.size() << endl;
 
    vector <int> num;
    for (auto e : real) {
        int x = 0;
        for (int i = 0; i < 10; ++i)
            if (g[e][bit[i]])
                x += 1 << i;
        num.app(x);
    }   
 
    /*
    InitMap( 3, 2 );
    MakeMap( 1, 2 );
    MakeMap( 1, 3 );
    */
 
    vector <ii> ans;
    for (int i = 0; i < real.size(); ++i)   
        for (int j = i+1; j < real.size(); ++j)
            if (g[real[i]][real[j]]) {
 
                //cout << "add " << num[i] << ' ' << num[j] << endl;
 
                ans.app(mp(num[i], num[j]));
            }
    InitMap(n, ans.size());
    for (auto e : ans)
        MakeMap(e.f, e.s);
}
 

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

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:107:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < bit.size(); ++i) {
                     ~~^~~~~~~~~~~~
Bob.cpp:115:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < bit.size(); ++i) {
                     ~~^~~~~~~~~~~~
Bob.cpp:117:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = i; j < bit.size(); ++j) {
                         ~~^~~~~~~~~~~~
Bob.cpp:149:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < real.size(); ++i)   
                     ~~^~~~~~~~~~~~~
Bob.cpp:150:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = i+1; j < real.size(); ++j)
                           ~~^~~~~~~~~~~~~

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