oj.uz

Submission #996550

# Submission time Handle Problem Language Result Execution time Memory
996550 2024-06-10T19:16:43 Z shmax Game (IOI14_game) C++14
100 / 100
 982 ms 158464 KB 
#include "game.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt")

using namespace std;
using namespace __gnu_pbds;
#define float long double
#define elif else if
#define endl "\n"
#define mod 1000000007
#define pi acos(-1)
#define eps 0.000000001
#define inf 1000'000'000'000'000'000LL
#define FIXED(a) cout << fixed << setprecision(a)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define time_init auto start = std::chrono::high_resolution_clock::now()
#define time_report                                       \
    auto end = std::chrono::high_resolution_clock::now(); \
    std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << " ms" << endl
#define debug(x) \
    { cerr << #x << " = " << x << endl; }
#define len(x) (int) x.size()
#define sqr(x) ((x) * (x))
#define cube(x) ((x) * (x) * (x))
#define bit(x, i) (((x) >> (i)) & 1)
#define set_bit(x, i) ((x) | (1LL << (i)))
#define clear_bit(x, i) ((x) & (~(1LL << (i))))
#define toggle_bit(x, i) ((x) ^ (1LL << (i)))
#define low_bit(x) ((x) & (-(x)))
#define count_bit(x) __builtin_popcountll(x)
#define srt(x) sort(all(x))
#define rsrt(x) sort(rall(x))
#define mp make_pair
#define maxel(x) (*max_element(all(x)))
#define minel(x) (*min_element(all(x)))
#define maxelpos(x) (max_element(all(x)) - x.begin())
#define minelpos(x) (min_element(all(x)) - x.begin())
#define sum(x) (accumulate(all(x), 0LL))
#define product(x) (accumulate(all(x), 1LL, multiplies<int>()))
#define gcd __gcd
#define lcm(a, b) ((a) / gcd(a, b) * (b))
#define rev(x) (reverse(all(x)))
#define shift_left(x, k) (rotate(x.begin(), x.begin() + k, x.end()))
#define shift_right(x, k) (rotate(x.rbegin(), x.rbegin() + k, x.rend()))
#define is_sorted(x) (is_sorted_until(all(x)) == x.end())
#define is_even(x) (((x) &1) == 0)
#define is_odd(x) (((x) &1) == 1)
#define pow2(x) (1LL << (x))

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }

    size_t operator()(std::pair<int, int> x) const {
        static const uint64_t FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count();
        uint64_t hash1 = splitmix64(x.first + FIXED_RANDOM);
        uint64_t hash2 = splitmix64(x.second + FIXED_RANDOM);
        return hash1 ^ (hash2 << 1); // Combine the two hashes
    }
};

template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using matrix = vector<vector<T>>;
template<typename T>
using graph = vector<vector<T>>;
template<typename U, typename V>
using hashmap = gp_hash_table<U, V, custom_hash>;
template<typename U>
using hashset = gp_hash_table<U, null_type, custom_hash>;

template<typename T>
vector<T> vect(int n, T val) {
    return vector<T>(n, val);
}

template<typename T>
vector<vector<T>> vect(int n, int m, T val) {
    return vector<vector<T>>(n, vector<T>(m, val));
}

template<typename T>
vector<vector<vector<T>>> vect(int n, int m, int k, T val) {
    return vector<vector<vector<T>>>(n, vector<vector<T>>(m, vector<T>(k, val)));
}

template<typename T>
vector<vector<vector<vector<T>>>> vect(int n, int m, int k, int l, T val) {
    return vector<vector<vector<vector<T>>>>(n, vector<vector<vector<T>>>(m, vector<vector<T>>(k, vector<T>(l, val))));
}

template<typename T>
matrix<T> new_matrix(int n, int m, T val) {
    return matrix<T>(n, vector<T>(m, val));
}

template<typename T>
graph<T> new_graph(int n) {
    return graph<T>(n);
}

template<class T, class S>
inline bool chmax(T &a, const S &b) {
    return (a < b ? a = b, 1 : 0);
}

template<class T, class S>
inline bool chmin(T &a, const S &b) {
    return (a > b ? a = b, 1 : 0);
}

using i8 = int8_t;
using i16 = int16_t;
using i32 = int32_t;
using i64 = int64_t;
using i128 = __int128_t;
using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using u128 = __uint128_t;

template<typename T>
using vec = vector<T>;

using pII = pair<int, int>;
template<typename T>
using enumerated = pair<T, int>;

vec<bitset<1501>> a;
vec<set<int>> g_mst;
hashset<pair<int, int>> edges;
hashset<pair<int, int>> MST_edges;
mt19937 rng(10235);


void initialize(int n) {
    g_mst.resize(n);
    a.resize(n);
    vec<int> p(n);
    iota(all(p), 0);
    shuffle(all(p), rng);
    for (int i = 1; i < n; i++) {
        MST_edges.insert({p[i], p[i - 1]});
        MST_edges.insert({p[i - 1], p[i]});
        g_mst[p[i]].insert(p[i - 1]);
        g_mst[p[i - 1]].insert(p[i]);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            if (MST_edges.find({i, j}) == MST_edges.end())
                edges.insert({i, j});
            a[i][j] = true;
        }
    }
}

int hasEdge(int u, int v) {
    if (edges.find({u, v}) != edges.end()) {
        edges.erase({u, v});
        edges.erase({v, u});
        a[v][u] = false;
        a[u][v] = false;
        return false;
    }
    a[u][v] = false;
    a[v][u] = false;
    g_mst[u].erase(v);
    g_mst[v].erase(u);


    bitset<1501> right;
    function<void(int, int)> dfs = [&](int v, int p) {
        right[v] = true;
        for (auto u: g_mst[v]) {
            if (u == p) continue;
            dfs(u, v);
        }
    };
    int n = len(g_mst);
    dfs(0, -1);
    if (len(edges) < n * 10) {
        int a_ = -1;
        int b_ = -1;
        for (auto [x, y]: edges) {
            if (right[x] xor right[y]) {
                a_ = x;
                b_ = y;

                break;
            }
        }
        if (a_ == -1) {
            a[u][v] = true;
            a[v][u] = true;
            g_mst[u].insert(v);
            g_mst[v].insert(u);
            return true;
        }

        edges.erase({a_, b_});
        edges.erase({b_, a_});
        g_mst[a_].insert(b_);
        g_mst[b_].insert(a_);
        return false;
    }


    for (int i = 0; i < n; i++) {
        if (right[i]) continue;
        bitset<1501> t = a[i] & right;
        if (t.count() != 0) {
            for (int j = 0; j < n; j++) {
                if (t[j]) {
                    edges.erase({i, j});
                    edges.erase({j, i});
                    g_mst[i].insert(j);
                    g_mst[j].insert(i);
                    return false;
                }
            }
        }
    }
    a[u][v] = true;
    a[v][u] = true;
    g_mst[u].insert(v);
    g_mst[v].insert(u);
    return true;
}

Compilation message

game.cpp: In function 'int hasEdge(int, int)':
game.cpp:209:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  209 |         for (auto [x, y]: edges) {
      |                   ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 344 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 2 ms 856 KB Output is correct
35 Correct 2 ms 856 KB Output is correct
36 Correct 2 ms 860 KB Output is correct
37 Correct 2 ms 856 KB Output is correct
38 Correct 2 ms 860 KB Output is correct
39 Correct 2 ms 860 KB Output is correct
40 Correct 2 ms 860 KB Output is correct
41 Correct 2 ms 692 KB Output is correct
42 Correct 2 ms 860 KB Output is correct
43 Correct 4 ms 860 KB Output is correct
44 Correct 2 ms 860 KB Output is correct
45 Correct 2 ms 860 KB Output is correct
46 Correct 2 ms 860 KB Output is correct
47 Correct 2 ms 860 KB Output is correct
48 Correct 2 ms 860 KB Output is correct
49 Correct 2 ms 860 KB Output is correct
50 Correct 2 ms 860 KB Output is correct
51 Correct 2 ms 860 KB Output is correct
52 Correct 2 ms 860 KB Output is correct
53 Correct 3 ms 860 KB Output is correct
54 Correct 2 ms 832 KB Output is correct

Subtask #3
58.0 / 58.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 600 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 600 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 1 ms 600 KB Output is correct
32 Correct 1 ms 516 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 2 ms 860 KB Output is correct
35 Correct 2 ms 860 KB Output is correct
36 Correct 2 ms 860 KB Output is correct
37 Correct 2 ms 860 KB Output is correct
38 Correct 2 ms 860 KB Output is correct
39 Correct 2 ms 860 KB Output is correct
40 Correct 2 ms 860 KB Output is correct
41 Correct 3 ms 856 KB Output is correct
42 Correct 2 ms 860 KB Output is correct
43 Correct 3 ms 860 KB Output is correct
44 Correct 1 ms 860 KB Output is correct
45 Correct 2 ms 860 KB Output is correct
46 Correct 2 ms 860 KB Output is correct
47 Correct 2 ms 860 KB Output is correct
48 Correct 2 ms 860 KB Output is correct
49 Correct 3 ms 860 KB Output is correct
50 Correct 2 ms 860 KB Output is correct
51 Correct 2 ms 860 KB Output is correct
52 Correct 2 ms 860 KB Output is correct
53 Correct 2 ms 860 KB Output is correct
54 Correct 2 ms 860 KB Output is correct
55 Correct 90 ms 21136 KB Output is correct
56 Correct 81 ms 21192 KB Output is correct
57 Correct 74 ms 21344 KB Output is correct
58 Correct 76 ms 21200 KB Output is correct
59 Correct 77 ms 21204 KB Output is correct
60 Correct 76 ms 21196 KB Output is correct
61 Correct 75 ms 21196 KB Output is correct
62 Correct 74 ms 21256 KB Output is correct
63 Correct 82 ms 21332 KB Output is correct
64 Correct 688 ms 21320 KB Output is correct
65 Correct 61 ms 21208 KB Output is correct
66 Correct 82 ms 21276 KB Output is correct
67 Correct 80 ms 21188 KB Output is correct
68 Correct 77 ms 21448 KB Output is correct
69 Correct 80 ms 21192 KB Output is correct
70 Correct 76 ms 21196 KB Output is correct
71 Correct 78 ms 21192 KB Output is correct
72 Correct 73 ms 21192 KB Output is correct
73 Correct 76 ms 21192 KB Output is correct
74 Correct 78 ms 21224 KB Output is correct
75 Correct 74 ms 21192 KB Output is correct
76 Correct 175 ms 39788 KB Output is correct
77 Correct 177 ms 39764 KB Output is correct
78 Correct 182 ms 39840 KB Output is correct
79 Correct 210 ms 39844 KB Output is correct
80 Correct 173 ms 39844 KB Output is correct
81 Correct 211 ms 39804 KB Output is correct
82 Correct 185 ms 39844 KB Output is correct
83 Correct 203 ms 39848 KB Output is correct
84 Correct 169 ms 39844 KB Output is correct
85 Correct 310 ms 39844 KB Output is correct
86 Correct 366 ms 43036 KB Output is correct
87 Correct 299 ms 43028 KB Output is correct
88 Correct 396 ms 42944 KB Output is correct
89 Correct 334 ms 43180 KB Output is correct
90 Correct 315 ms 43180 KB Output is correct
91 Correct 381 ms 43176 KB Output is correct
92 Correct 357 ms 42972 KB Output is correct
93 Correct 300 ms 43176 KB Output is correct
94 Correct 859 ms 158352 KB Output is correct
95 Correct 982 ms 158348 KB Output is correct
96 Correct 860 ms 158360 KB Output is correct
97 Correct 887 ms 158464 KB Output is correct
98 Correct 911 ms 158360 KB Output is correct
99 Correct 862 ms 158392 KB Output is correct
100 Correct 874 ms 158360 KB Output is correct