Submission #242775

#	Time	Username	Problem	Language	Result	Execution time	Memory
242775		osaaateiasavtnl	Airline Route Map (JOI18_airline)	C++17	22 / 100	821 ms	30832 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[] ){   
    /*
    InitG( 3, 2 );
    MakeG( 1, 2 );
    MakeG( 1, 3 );
    */

    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, N + 11 - centers
    ans.app(mp(N+10, N+11));
    for (int i = 0; i < N; ++i) {
        ans.app(mp(i, N + 10));
        ans.app(mp(i, N + 11));
    }       

    for (int i = N+1; i < N + 10; i += 2)
        ans.app(mp(i, N + 10));
    for (int i = N+2; i < N + 10; i += 2)
        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 = N; i < N + 10; ++i) {
        if (pw[i] >= min(pw[N+10], pw[N+11])) {
            cout << "LMAO bit " << i - N << ' ' << pw[i] << endl;
            exit(1);
        }   
    }   

    for (int i = 0; i < N; ++i) {
        if (pw[i] >= min(pw[N+10], pw[N+11])) {
            cout << "LMAO vertex " << i << ' ' << pw[i] << endl;
            exit(1);
        }   
    }
    */  

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

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

    vector <int> cen = {ord[V - 2], ord[V - 1]};
    vector <int> bit;
    for (int i = 0; i < V; ++i) {
        int tocen = 0;
        for (auto e : cen) {
            tocen += g[i][e];
            if (e == i)
                tocen += 100;
        }
        if (tocen < 2) {
            bit.app(i);
        }   
    }   

    for (int i = 0; i < bit.size(); ++i) {
        int tocen = 0;
        for (auto e : cen) {
            tocen += g[bit[i]][e];
            if (e == bit[i])
                tocen += 100;
        }
        if (tocen == 0) {
            swap(bit[0], bit[i]);
            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][cen[0]] || !g[i][cen[1]])
            continue;
        real.app(i);
    }   

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

Compilation message (stderr)

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:48:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < bit.size(); ++i) {
                     ~~^~~~~~~~~~~~
Bob.cpp:61:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < bit.size(); ++i) {
                     ~~^~~~~~~~~~~~
Bob.cpp:63:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = i; j < bit.size(); ++j) {
                         ~~^~~~~~~~~~~~
Bob.cpp:94:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < real.size(); ++i)   
                     ~~^~~~~~~~~~~~~
Bob.cpp:95: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: 0 / 15
• Subtask 3: 0 / 63