oj.uz

Submission #987811

# Submission time Handle Problem Language Result Execution time Memory
987811 2024-05-23T15:49:58 Z steveonalex Werewolf (IOI18_werewolf) C++17
100 / 100
 1179 ms 124956 KB 
#include <bits/stdc++.h>
#include "werewolf.h"
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
 
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ll mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}
 
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
 
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b) {a = b; return true;}
        return false;
    }
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b) {a = b; return true;}
        return false;
    }
 
template <class T>
    void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
        for(auto item: container) out << item << separator;
        out << finish;
    }
 
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

struct DSU{
    int n;
    vector<int> parent, sz;
    vector<vector<pair<int, int>>> chain;

    DSU(int _n){
        n = _n;
        parent.resize(n); sz.resize(n, 1);
        chain.resize(n);
        for(int i = 0; i<n; ++i){
            parent[i] = i;
            chain[i].push_back({i, -1});
        }
    }

    int find_set(int u){return (u == parent[u]) ? u : (parent[u] = find_set(parent[u]));}
    bool same_set(int u, int v){return find_set(u) != find_set(v);}

    bool join_set(int u, int v, int w = -1){
        u = find_set(u), v = find_set(v);
        if (u != v){
            if (sz[u] < sz[v]) swap(u, v);
            parent[v] = u;
            sz[u] += sz[v];
            chain[u].back().second = w;
            for(pair<int, int> i: chain[v]){
                chain[u].push_back(i);
            }
            chain[v].clear();
            return true;
        }
        return false;
    }

    vector<pair<int, int>> get_chain(){
        return chain[find_set(0)];
    }
};

struct FenwickTree{
    int n;
    vector<int> a;

    FenwickTree(int _n){
        n = _n;
        a.resize(n+1);
    }

    void update(int i, int w){
        while(i <= n){
            a[i] += w;
            i += LASTBIT(i);
        }
    }

    int get(int i){
        int ans = 0;
        while(i > 0){
            ans += a[i];
            i -= LASTBIT(i);
        }
        return ans;
    }

    int get(int l, int r){return get(r) - get(l-1);}
};

const int N = 2e5 + 69, LOG_N = 18, INF = 1e9 + 69;

int n, m, q;
int chain1[N], chain2[N];
int pos1[N], pos2[N];
int w1[LOG_N][N], w2[LOG_N][N];

int min_w(int l, int r){
    if (l > r) swap(l, r);
    if (l == r) return INF;
    r--;
    int j = logOf(r - l + 1);
    return min(w1[j][l], w1[j][r - MASK(j) + 1]);
}

int max_w(int l, int r){
    if (l > r) swap(l, r);
    if (l == r) return -INF;
    r--;
    int j = logOf(r - l + 1);
    return max(w2[j][l], w2[j][r - MASK(j) + 1]);
}

pair<int, int> spread_min(int p, int cap){
    pair<int, int> ans = {p, p};
    int l = 0, r = p;
    while(l < r){
        int mid = (l + r) >> 1;
        if (min_w(mid, p) >= cap) r = mid;
        else l = mid + 1;
    }
    ans.first = l;
    l = p, r = n-1;
    while(l < r){
        int mid = (l + r + 1) >> 1;
        if (min_w(p, mid) >= cap) l = mid;
        else r = mid - 1;
    }
    ans.second = l;
    return ans;
}

pair<int, int> spread_max(int p, int cap){
    pair<int, int> ans = {p, p};
    int l = 0, r = p;
    while(l < r){
        int mid = (l + r) >> 1;
        if (max_w(mid, p) <= cap) r = mid;
        else l = mid + 1;
    }
    ans.first = l;
    l = p, r = n-1;
    while(l < r){
        int mid = (l + r + 1) >> 1;
        if (max_w(mid, p) <= cap) l = mid;
        else r = mid - 1;
    }
    ans.second = l;
    return ans;
}

int query[N];
vector<array<int, 3>> createQuery[N], destroyQuery[N];

vector<int> check_validity(int _n, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {
    n = _n, m = X.size();
    q = S.size();

    vector<int> ans(q);

    // build tree line for minimum node
    vector<array<int, 3>> min_edge(m);
    for(int i = 0; i<m; ++i)
        min_edge[i] = {{X[i], Y[i], min(X[i], Y[i])}};

    sort(ALL(min_edge), [](array<int, 3> x, array<int, 3> y){return x[2] > y[2];});

    DSU mst_min(n);
    for(auto i: min_edge)
        mst_min.join_set(i[0], i[1], i[2]);
    vector<pair<int,int>> min_chain = mst_min.get_chain();


    // build tree line for maximum node
    vector<array<int, 3>> max_edge(m);
    for(int i = 0; i<m; ++i)
        max_edge[i] = {{X[i], Y[i], max(X[i], Y[i])}};
    sort(ALL(max_edge), [](array<int, 3> x, array<int, 3> y){return x[2] < y[2];});

    DSU mst_max(n);
    for(auto i: max_edge)
        mst_max.join_set(i[0], i[1], i[2]);
    vector<pair<int,int>> max_chain = mst_max.get_chain();

    for(int i = 0; i<n; ++i) {
        chain1[i] = min_chain[i].first;
        pos1[chain1[i]] = i;

        chain2[i] = max_chain[i].first;
        pos2[chain2[i]] = i;

        w1[0][i] = min_chain[i].second;
        w2[0][i] = max_chain[i].second;
    }

    for(int j = 1; MASK(j) <= n; ++j)
    for(int i = 0; i + MASK(j) <= n; ++i){
        w1[j][i] = min(w1[j-1][i], w1[j-1][i + MASK(j-1)]);
        w2[j][i] = max(w2[j-1][i], w2[j-1][i + MASK(j-1)]);
    }

    for(int i = 0; i<n; ++i) query[pos1[i] + 1] = pos2[i] + 1;

    for(int i = 0; i < q; ++i){
        pair<int, int> spread1 = spread_min(pos1[S[i]], L[i]);
        pair<int, int> spread2 = spread_max(pos2[E[i]], R[i]);
        spread1.first++; spread1.second++; spread2.first++; spread2.second++;
        destroyQuery[spread1.first-1].push_back({{spread2.first, spread2.second, i}});
        createQuery[spread1.second].push_back({{spread2.first, spread2.second, i}});
    }

    FenwickTree bit(n);
    for(int i = 1; i<=n; ++i){
        bit.update(query[i], 1);
        for(array<int, 3> j: destroyQuery[i]){
            ans[j[2]] -= bit.get(j[0], j[1]);
        }
        for(array<int, 3> j: createQuery[i]){
            ans[j[2]] += bit.get(j[0], j[1]);
        }
    }

    for(int i = 0; i<q; ++i) ans[i] = (ans[i] > 0);

    return ans;
}



// int main(void){
//     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//     int n, m, q; cin >> n >> m >> q;
//     vector<int> X, Y;
//     for(int i = 0; i<m; ++i){
//         int u, v; cin >> u >> v;
//         X.push_back(u); Y.push_back(v);
//     }

//     vector<int> S(q), E(q), L(q), R(q);
//     for(int i = 0; i<q; ++i){
//         cin >> S[i] >> E[i] >> L[i] >> R[i];
//     }

//     printArr(check_validity(n, X, Y, S, E, L, R));

//     return 0;
// }

Compilation message

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:222:28: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'int' [-Wsign-compare]
  222 |     for(int j = 1; MASK(j) <= n; ++j)
      |                            ^
werewolf.cpp:223:32: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'int' [-Wsign-compare]
  223 |     for(int i = 0; i + MASK(j) <= n; ++i){
      |                    ~~~~~~~~~~~~^~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 29276 KB Output is correct
2 Correct 7 ms 29276 KB Output is correct
3 Correct 6 ms 25176 KB Output is correct
4 Correct 5 ms 21084 KB Output is correct
5 Correct 7 ms 29276 KB Output is correct
6 Correct 7 ms 29276 KB Output is correct
7 Correct 7 ms 29276 KB Output is correct
8 Correct 7 ms 29352 KB Output is correct
9 Correct 7 ms 29276 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 29276 KB Output is correct
2 Correct 7 ms 29276 KB Output is correct
3 Correct 6 ms 25176 KB Output is correct
4 Correct 5 ms 21084 KB Output is correct
5 Correct 7 ms 29276 KB Output is correct
6 Correct 7 ms 29276 KB Output is correct
7 Correct 7 ms 29276 KB Output is correct
8 Correct 7 ms 29352 KB Output is correct
9 Correct 7 ms 29276 KB Output is correct
10 Correct 15 ms 36444 KB Output is correct
11 Correct 11 ms 36444 KB Output is correct
12 Correct 14 ms 36440 KB Output is correct
13 Correct 12 ms 36444 KB Output is correct
14 Correct 11 ms 36440 KB Output is correct
15 Correct 12 ms 36444 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1111 ms 116288 KB Output is correct
2 Correct 559 ms 106920 KB Output is correct
3 Correct 455 ms 111504 KB Output is correct
4 Correct 650 ms 117212 KB Output is correct
5 Correct 618 ms 116516 KB Output is correct
6 Correct 795 ms 120124 KB Output is correct
7 Correct 629 ms 124956 KB Output is correct
8 Correct 434 ms 107056 KB Output is correct
9 Correct 352 ms 112480 KB Output is correct
10 Correct 342 ms 116156 KB Output is correct
11 Correct 396 ms 116272 KB Output is correct
12 Correct 376 ms 120228 KB Output is correct
13 Correct 547 ms 105588 KB Output is correct
14 Correct 498 ms 105660 KB Output is correct
15 Correct 556 ms 105756 KB Output is correct
16 Correct 627 ms 105712 KB Output is correct
17 Correct 748 ms 124884 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 29276 KB Output is correct
2 Correct 7 ms 29276 KB Output is correct
3 Correct 6 ms 25176 KB Output is correct
4 Correct 5 ms 21084 KB Output is correct
5 Correct 7 ms 29276 KB Output is correct
6 Correct 7 ms 29276 KB Output is correct
7 Correct 7 ms 29276 KB Output is correct
8 Correct 7 ms 29352 KB Output is correct
9 Correct 7 ms 29276 KB Output is correct
10 Correct 15 ms 36444 KB Output is correct
11 Correct 11 ms 36444 KB Output is correct
12 Correct 14 ms 36440 KB Output is correct
13 Correct 12 ms 36444 KB Output is correct
14 Correct 11 ms 36440 KB Output is correct
15 Correct 12 ms 36444 KB Output is correct
16 Correct 1111 ms 116288 KB Output is correct
17 Correct 559 ms 106920 KB Output is correct
18 Correct 455 ms 111504 KB Output is correct
19 Correct 650 ms 117212 KB Output is correct
20 Correct 618 ms 116516 KB Output is correct
21 Correct 795 ms 120124 KB Output is correct
22 Correct 629 ms 124956 KB Output is correct
23 Correct 434 ms 107056 KB Output is correct
24 Correct 352 ms 112480 KB Output is correct
25 Correct 342 ms 116156 KB Output is correct
26 Correct 396 ms 116272 KB Output is correct
27 Correct 376 ms 120228 KB Output is correct
28 Correct 547 ms 105588 KB Output is correct
29 Correct 498 ms 105660 KB Output is correct
30 Correct 556 ms 105756 KB Output is correct
31 Correct 627 ms 105712 KB Output is correct
32 Correct 748 ms 124884 KB Output is correct
33 Correct 1179 ms 111724 KB Output is correct
34 Correct 281 ms 74276 KB Output is correct
35 Correct 742 ms 108256 KB Output is correct
36 Correct 931 ms 113512 KB Output is correct
37 Correct 810 ms 108716 KB Output is correct
38 Correct 920 ms 112924 KB Output is correct
39 Correct 775 ms 110588 KB Output is correct
40 Correct 683 ms 118576 KB Output is correct
41 Correct 458 ms 107480 KB Output is correct
42 Correct 349 ms 112416 KB Output is correct
43 Correct 494 ms 111548 KB Output is correct
44 Correct 522 ms 107876 KB Output is correct
45 Correct 352 ms 108112 KB Output is correct
46 Correct 395 ms 108844 KB Output is correct
47 Correct 572 ms 105768 KB Output is correct
48 Correct 599 ms 105752 KB Output is correct
49 Correct 533 ms 105772 KB Output is correct
50 Correct 597 ms 105540 KB Output is correct
51 Correct 509 ms 118332 KB Output is correct
52 Correct 581 ms 118332 KB Output is correct