Submission #129914

#	Time	Username	Problem	Language	Result	Execution time	Memory
129914		BThero	Airline Route Map (JOI18_airline)	C++17	37 / 100	720 ms	15700 KiB

Alice

// Why am I so dumb? :c
// chrono::system_clock::now().time_since_epoch().count()

//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include "Alicelib.h"

#define pb push_back
#define mp make_pair

#define all(x) (x).begin(), (x).end()

#define fi first
#define se second

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef pair<int, int> pii;   
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

void Alice(int n, int m, int A[], int B[]) {
    vector<pii> e;

    for (int i = 0; i < m; ++i) {
        e.pb(mp(A[i], B[i]));
    }  

    for (int i = 0; i < n; ++i) {
        e.pb(mp(n + i, 2 * n));

        for (int j = 0; j <= i; ++j) {
            e.pb(mp(i, n + j));
        }
    }

    for (int i = 0; i < 2 * n; ++i) {
        e.pb(mp(i, 2 * n + 1));
    }

    InitG(2 * n + 2, (int)e.size());

    for (int i = 0; i < e.size(); ++i) {
        MakeG(i, e[i].fi, e[i].se);
    }
}

Bob

// Why am I so dumb? :c
// chrono::system_clock::now().time_since_epoch().count()

//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include "Boblib.h"

#define pb push_back
#define mp make_pair

#define all(x) (x).begin(), (x).end()

#define fi first
#define se second

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;   
typedef pair<int, int> pii;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int MAXN = (int)2e3 + 5;

static int deg[MAXN], rl[MAXN];

static bool adj[MAXN][MAXN];

static bool our[MAXN];

void Bob(int n, int m, int A[], int B[]) {
    int _n = (n - 2) / 2;

    for (int i = 0; i < m; ++i) {
        adj[A[i]][B[i]] = 1;
        adj[B[i]][A[i]] = 1;
        ++deg[A[i]];
        ++deg[B[i]];
    }

    int me = 0, boss = 0;

    while (deg[boss] != n - 2) {
        ++boss;
    }

    for (int i = 0; i < n; ++i) {
        if (i != boss && !adj[boss][i]) {
            me = i;
        }
    }

    for (int i = 0; i < n; ++i) {
        if (i == me || i == boss || adj[i][me]) {
            our[i] = 0;
        }
        else {
            our[i] = 1;
        }
    }

    for (int i = 0; i < n; ++i) {
        if (i != me && i != boss && !our[i]) {
            for (int j = 0; j < n; ++j) {
                if (adj[i][j]) {
                    ++rl[j];
                }
            }
        }
    }

    vector<pii> e;
    
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (our[i] && our[j] && adj[i][j]) {
                e.pb(mp(rl[i] - 1, rl[j] - 1));
            }
        }
    }

    InitMap(_n, e.size());

    for (int i = 0; i < e.size(); ++i) {
        MakeMap(e[i].fi, e[i].se);
    }
}

Compilation message (stderr)

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:48:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < e.size(); ++i) {
                     ~~^~~~~~~~~~

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:88:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < e.size(); ++i) {
                     ~~^~~~~~~~~~

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