oj.uz

Submission #130161

# Submission time Handle Problem Language Result Execution time Memory
130161 2019-07-14T06:07:03 Z BThero Airline Route Map (JOI18_airline) C++17
37 / 100
 966 ms 38584 KB 
// 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>;

static const int MAXN = (int)1e3 + 5;

static pii e[MAXN * MAXN];

static int n, m;

void buildBad() {
    vector<pii> _e;

    for (int i = 0; i < m; ++i) {
        _e.pb(e[i]);
    }

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

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

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

    InitG(n + n + 2, _e.size());

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

void buildGood() {
    int k = 0;

    while ((1 << k) < n) {
        ++k;
    }

    vector<pii> _e;

    for (int i = 0; i < m; ++i) {
        _e.pb(e[i]);
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < k; ++j) {
            if (i & (1 << j)) {
                _e.pb(mp(i, n + j));
            }
        }
    }

    for (int i = 0; i < k; ++i) {
        _e.pb(mp(n + i, n + i + 1));
        _e.pb(mp(n + i, n + k + 1));
    }

    _e.pb(mp(n + k, n + k + 1));
    _e.pb(mp(n + k - 2, n + k));

    for (int i = 0; i <= n + k; ++i) {
        _e.pb(mp(i, n + k + 2));
    }

    InitG(n + k + 3, _e.size());

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

void Alice(int _n, int _m, int A[], int B[]) {
    n = _n;
    m = _m;

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

    if (n <= 10) {
        buildBad();
    }
    else {
        buildGood();
    }
}


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

static const int MAXN = (int)2e3 + 5;
static const int INF = (int)1e9;

static int id[MAXN], deg[MAXN], tp[MAXN];

static bool adj[MAXN][MAXN];

static int dep[MAXN];

static pii e[MAXN];

static int n, m;

void solve() {
    vector<pii> _e;

    for (int i = 0; i < m; ++i) {
        int u = e[i].fi;
        int v = e[i].se;
        ++deg[u];
        ++deg[v];
        adj[u][v] = 1;
        adj[v][u] = 1;
    }

    int boss = 0, me = 0, cnt = 0;

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

    while (me == boss || adj[boss][me]) {
        ++me;
    }

    for (int i = 0; i < n; ++i) {
        if (i == me) {
            tp[i] = 2;
        }
        else if (i == boss) {
            tp[i] = 3;
        }
        else {
            if (adj[i][me]) {
                tp[i] = 0;
                ++cnt;
            }
            else {
                tp[i] = 1;
            }
        }
    }

    int _n = 0;

    if (cnt * 2 + 2 == n) {
        _n = cnt;

        for (int i = 0; i < n; ++i) {
            if (tp[i] == 0) {
                for (int j = 0; j < n; ++j) {
                    if (tp[j] == 1 && adj[i][j]) {
                        ++id[j];
                    }
                }
            }
        }

        for (int i = 0; i < n; ++i) {
            if (tp[i] == 1) {
                for (int j = i + 1; j < n; ++j) {
                    if (tp[j] == 1 && adj[i][j]) {
                        _e.pb(mp(id[i], id[j]));
                    }
                }
            }
        }

        InitMap(_n, _e.size());

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

        return;
    }

    fill(deg, deg + n, 0);

    for (int i = 0; i < n; ++i) {
        if (tp[i] == 1) {
            ++_n;
        }                
    }

    for (int i = 0; i < m; ++i) {
        int u = e[i].fi;
        int v = e[i].se;

        if (tp[u] == 0 && tp[v] == 0) {
            ++deg[u];
            ++deg[v];
        }
    }

    int meshok = -1;

    for (int i = 0; i < n; ++i) {
        if (tp[i] == 0) {
            if (meshok == -1 || deg[i] < deg[meshok]) {
                meshok = i;
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        if (tp[i] == 0) {
            dep[i] = INF;
        }
    }

    queue<int> q;
    q.push(meshok);
    dep[meshok] = 0;

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        for (int to = 0; to < n; ++to) {
            if (tp[to] == 0 && adj[v][to] && dep[to] > dep[v] + 1) {
                dep[to] = dep[v] + 1;
                q.push(to);
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        if (tp[i] == 0) {
            for (int j = 0; j < n; ++j) {
                if (tp[j] == 1 && adj[i][j]) {
                    id[j] += (1 << dep[i]);
                }
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        if (tp[i] == 1) {
            for (int j = i + 1; j < n; ++j) {
                if (tp[j] == 1) {
                    if (adj[i][j]) {
                        _e.pb(mp(id[i], id[j]));
                    }
                }
            }
        }
    }

    InitMap(_n, _e.size());

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

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

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

    solve();
}

Compilation message

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

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

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6648 KB Output is correct
2 Correct 9 ms 6640 KB Output is correct
3 Correct 9 ms 6896 KB Output is correct
4 Correct 8 ms 6896 KB Output is correct
5 Correct 9 ms 6896 KB Output is correct
6 Correct 8 ms 6640 KB Output is correct
7 Correct 10 ms 6640 KB Output is correct
8 Correct 8 ms 6640 KB Output is correct
9 Correct 8 ms 6640 KB Output is correct
10 Correct 9 ms 6640 KB Output is correct
11 Correct 8 ms 6648 KB Output is correct
12 Correct 9 ms 6896 KB Output is correct
13 Correct 9 ms 6640 KB Output is correct
14 Correct 9 ms 6736 KB Output is correct
15 Correct 9 ms 6640 KB Output is correct
16 Correct 8 ms 6648 KB Output is correct
17 Correct 8 ms 6640 KB Output is correct
18 Correct 9 ms 6896 KB Output is correct
19 Correct 8 ms 6640 KB Output is correct
20 Correct 9 ms 6904 KB Output is correct
21 Correct 9 ms 6664 KB Output is correct
22 Correct 8 ms 6648 KB Output is correct
23 Correct 9 ms 6896 KB Output is correct
24 Correct 9 ms 6896 KB Output is correct
25 Correct 8 ms 6640 KB Output is correct
26 Correct 8 ms 6640 KB Output is correct
27 Correct 9 ms 6640 KB Output is correct
28 Correct 8 ms 6640 KB Output is correct
29 Correct 10 ms 6896 KB Output is correct
30 Correct 10 ms 6904 KB Output is correct
31 Correct 9 ms 6736 KB Output is correct
32 Correct 8 ms 6640 KB Output is correct
33 Correct 9 ms 6640 KB Output is correct
34 Correct 8 ms 6640 KB Output is correct
35 Correct 9 ms 6640 KB Output is correct
36 Correct 9 ms 6896 KB Output is correct
37 Correct 9 ms 6640 KB Output is correct
38 Correct 9 ms 6896 KB Output is correct
39 Correct 8 ms 6640 KB Output is correct
40 Correct 9 ms 6896 KB Output is correct
41 Correct 9 ms 6736 KB Output is correct
42 Correct 9 ms 6896 KB Output is correct
43 Correct 9 ms 6896 KB Output is correct
44 Correct 9 ms 6640 KB Output is correct
45 Correct 9 ms 6640 KB Output is correct
46 Correct 8 ms 6640 KB Output is correct
47 Correct 8 ms 6640 KB Output is correct
48 Correct 9 ms 6896 KB Output is correct
49 Correct 9 ms 6640 KB Output is correct
50 Correct 9 ms 6640 KB Output is correct
51 Correct 9 ms 6640 KB Output is correct
52 Correct 9 ms 6640 KB Output is correct
53 Correct 9 ms 6640 KB Output is correct
54 Correct 9 ms 6640 KB Output is correct
55 Correct 9 ms 6736 KB Output is correct
56 Correct 9 ms 6896 KB Output is correct
57 Correct 9 ms 6896 KB Output is correct
58 Correct 9 ms 6896 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6648 KB Output is correct
2 Correct 9 ms 6640 KB Output is correct
3 Correct 9 ms 6896 KB Output is correct
4 Correct 8 ms 6896 KB Output is correct
5 Correct 9 ms 6896 KB Output is correct
6 Correct 8 ms 6640 KB Output is correct
7 Correct 10 ms 6640 KB Output is correct
8 Correct 8 ms 6640 KB Output is correct
9 Correct 8 ms 6640 KB Output is correct
10 Correct 9 ms 6640 KB Output is correct
11 Correct 8 ms 6648 KB Output is correct
12 Correct 9 ms 6896 KB Output is correct
13 Correct 9 ms 6640 KB Output is correct
14 Correct 9 ms 6736 KB Output is correct
15 Correct 9 ms 6640 KB Output is correct
16 Correct 8 ms 6648 KB Output is correct
17 Correct 8 ms 6640 KB Output is correct
18 Correct 9 ms 6896 KB Output is correct
19 Correct 8 ms 6640 KB Output is correct
20 Correct 9 ms 6904 KB Output is correct
21 Correct 9 ms 6664 KB Output is correct
22 Correct 8 ms 6648 KB Output is correct
23 Correct 9 ms 6896 KB Output is correct
24 Correct 9 ms 6896 KB Output is correct
25 Correct 8 ms 6640 KB Output is correct
26 Correct 8 ms 6640 KB Output is correct
27 Correct 9 ms 6640 KB Output is correct
28 Correct 8 ms 6640 KB Output is correct
29 Correct 10 ms 6896 KB Output is correct
30 Correct 10 ms 6904 KB Output is correct
31 Correct 9 ms 6736 KB Output is correct
32 Correct 8 ms 6640 KB Output is correct
33 Correct 9 ms 6640 KB Output is correct
34 Correct 8 ms 6640 KB Output is correct
35 Correct 9 ms 6640 KB Output is correct
36 Correct 9 ms 6896 KB Output is correct
37 Correct 9 ms 6640 KB Output is correct
38 Correct 9 ms 6896 KB Output is correct
39 Correct 8 ms 6640 KB Output is correct
40 Correct 9 ms 6896 KB Output is correct
41 Correct 9 ms 6736 KB Output is correct
42 Correct 9 ms 6896 KB Output is correct
43 Correct 9 ms 6896 KB Output is correct
44 Correct 9 ms 6640 KB Output is correct
45 Correct 9 ms 6640 KB Output is correct
46 Correct 8 ms 6640 KB Output is correct
47 Correct 8 ms 6640 KB Output is correct
48 Correct 9 ms 6896 KB Output is correct
49 Correct 9 ms 6640 KB Output is correct
50 Correct 9 ms 6640 KB Output is correct
51 Correct 9 ms 6640 KB Output is correct
52 Correct 9 ms 6640 KB Output is correct
53 Correct 9 ms 6640 KB Output is correct
54 Correct 9 ms 6640 KB Output is correct
55 Correct 9 ms 6736 KB Output is correct
56 Correct 9 ms 6896 KB Output is correct
57 Correct 9 ms 6896 KB Output is correct
58 Correct 9 ms 6896 KB Output is correct
59 Correct 9 ms 6640 KB Output is correct
60 Correct 9 ms 6648 KB Output is correct
61 Correct 9 ms 6640 KB Output is correct
62 Correct 11 ms 6896 KB Output is correct
63 Correct 9 ms 6640 KB Output is correct
64 Correct 10 ms 6640 KB Output is correct
65 Correct 10 ms 6648 KB Output is correct
66 Correct 9 ms 6896 KB Output is correct
67 Correct 9 ms 6640 KB Output is correct
68 Correct 9 ms 6640 KB Output is correct
69 Correct 9 ms 6640 KB Output is correct
70 Correct 9 ms 6640 KB Output is correct
71 Correct 9 ms 6640 KB Output is correct
72 Correct 9 ms 6640 KB Output is correct
73 Correct 9 ms 6640 KB Output is correct
74 Correct 9 ms 6640 KB Output is correct
75 Correct 9 ms 6640 KB Output is correct
76 Correct 9 ms 6640 KB Output is correct
77 Correct 9 ms 6640 KB Output is correct
78 Correct 9 ms 6640 KB Output is correct
79 Correct 9 ms 6640 KB Output is correct
80 Correct 9 ms 6896 KB Output is correct
81 Correct 9 ms 6640 KB Output is correct
82 Correct 10 ms 6896 KB Output is correct
83 Correct 9 ms 6896 KB Output is correct
84 Correct 9 ms 6640 KB Output is correct
85 Correct 10 ms 6640 KB Output is correct
86 Correct 9 ms 6640 KB Output is correct
87 Correct 9 ms 6896 KB Output is correct
88 Correct 9 ms 6952 KB Output is correct
89 Correct 9 ms 6640 KB Output is correct
90 Correct 9 ms 7152 KB Output is correct
91 Correct 8 ms 6640 KB Output is correct
92 Correct 9 ms 6896 KB Output is correct
93 Correct 9 ms 6640 KB Output is correct
94 Correct 9 ms 6640 KB Output is correct
95 Correct 9 ms 6640 KB Output is correct
96 Correct 9 ms 6736 KB Output is correct
97 Correct 9 ms 6896 KB Output is correct
98 Correct 9 ms 6640 KB Output is correct
99 Correct 9 ms 6824 KB Output is correct
100 Correct 9 ms 6896 KB Output is correct
101 Correct 9 ms 6896 KB Output is correct
102 Correct 9 ms 6896 KB Output is correct
103 Correct 8 ms 6640 KB Output is correct
104 Correct 8 ms 6640 KB Output is correct
105 Correct 9 ms 6640 KB Output is correct
106 Correct 9 ms 6640 KB Output is correct
107 Correct 8 ms 6640 KB Output is correct
108 Correct 9 ms 6640 KB Output is correct
109 Correct 9 ms 6896 KB Output is correct
110 Correct 9 ms 6896 KB Output is correct
111 Correct 9 ms 6896 KB Output is correct
112 Correct 9 ms 6640 KB Output is correct
113 Correct 9 ms 6896 KB Output is correct
114 Correct 9 ms 6640 KB Output is correct
115 Correct 9 ms 6640 KB Output is correct
116 Correct 9 ms 6896 KB Output is correct
117 Correct 9 ms 6640 KB Output is correct
118 Correct 9 ms 6640 KB Output is correct

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Runtime error 966 ms 38584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -