Submission #954416

#	Time	Username	Problem	Language	Result	Execution time	Memory
954416		efishel	Airline Route Map (JOI18_airline)	C++17	37 / 100	3083 ms	40956 KiB

Alice

#include "Alicelib.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
#include <vector>
using namespace std;
using ll = long long;
using vll = vector <ll>;

void Alice (int n, int m, int A[], int B[]) {
    bool mat[n][n]{};
    for (ll i = 0; i < m; i++) {
        mat[A[i]][B[i]] = true;
        mat[B[i]][A[i]] = true;
    }
    vector <bool> th;
    for (ll i = 0; i < n; i++) {
        for (ll j = i; j < n; j++) {
            th.push_back(mat[i][j]);
        }
    }
    vector <pair <ll, ll> > egs;
    for (ll i = 0; i < th.size(); i++) {
        egs.push_back({ i, i+1 });
        if (th[i]) egs.push_back({ 0, i+1 });
    }
    for (auto [u, v] : egs) cerr << u << ' ' << v << '\n';
    InitG(th.size()+1+6, egs.size()+9);
    ll i=th.size()+2;
    for (ll j = 0; j < 4; j++) egs.push_back({ i+j, i+j+1 });
    for (ll j = i; j < i+5; j++) egs.push_back({ 0, j });
    ll timer=0;
    for (auto [u, v] : egs) MakeG(timer++, u, v);
}

Bob

#include "Boblib.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
#include <vector>
using namespace std;
using ll = long long;
using vll = vector <ll>;

const ll MAXN = 1E6+16;
vll adj[MAXN];

void Bob (int n, int m, int A[], int B[]) {
    cerr << "BOB\n";
    for (ll i = 0; i < m; i++) {
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
        cerr << A[i] << ' ' << B[i] << '\n';
    }
    cerr << "\n";
    ll sp = -15, best=0;
    ll nd = -15;
    for (ll i = 0; i < n; i++) {
        if (adj[i].size() > best) best = adj[i].size(), sp = i;
        if (adj[i].size() == 1) nd = i;
    }
    cerr << "special: " << sp << '\n';
    cerr << "end: " << nd << '\n';
    vector <bool> th;
    function <void(ll, ll)> dfs = [&](ll u, ll par) {
        bool has1 = false;
        for (ll v : adj[u]) {
            if (v == sp) { has1 = true; continue; }
            if (v == par) continue;
            dfs(v, u);
        }
        th.push_back(has1);
    };
    dfs(nd, nd);
    ll nn = 0;
    while (nn*(nn+1)/2 < th.size()) nn++;
    bool mat[nn][nn]{};
    ll c = 0;
    vector <pair <ll, ll> > egs;
    for (ll i = 0; i < nn; i++) {
        for (ll j = i; j < nn; j++) {
            if (th[c++] && !(i==0 && j==0)) egs.push_back({ i, j });
        }
    }
    for (auto [u, v] : egs) cerr << u << ' ' << v << '\n';
    InitMap(nn, egs.size());
    for (auto [u, v] : egs) MakeMap(u, v);
}

Compilation message (stderr)

Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:23:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for (ll i = 0; i < th.size(); i++) {
      |                    ~~^~~~~~~~~~~

Bob.cpp: In function 'void Bob(int, int, int*, int*)':
Bob.cpp:24:27: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   24 |         if (adj[i].size() > best) best = adj[i].size(), sp = i;
      |             ~~~~~~~~~~~~~~^~~~~~
Bob.cpp:41:24: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     while (nn*(nn+1)/2 < th.size()) nn++;
      |            ~~~~~~~~~~~~^~~~~~~~~~~
Bob.cpp:42:10: warning: unused variable 'mat' [-Wunused-variable]
   42 |     bool mat[nn][nn]{};
      |          ^~~

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