oj.uz

Submission #516193

# Submission time Handle Problem Language Result Execution time Memory
516193 2022-01-20T15:15:22 Z pokmui9909 Werewolf (IOI18_werewolf) C++17
100 / 100
 1414 ms 227068 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll S = (1 << 20);
class MergeSortTree{
public:
    ll query(ll l, ll r, ll mn, ll mx) {return query(1, 1, S / 2, l, r, mn, mx);}
    void init(){
        for(int i = S / 2 - 1; i >= 1; i--){
            vector<ll> &L = T[i * 2], &R = T[i * 2 + 1];
            T[i].resize(L.size() + R.size());
            merge(L.begin(), L.end(), R.begin(), R.end(), T[i].begin());
        }
    }
    void push(ll k, ll v){
        T[k + S / 2 - 1].push_back(v);
    }
    bool query(ll node, ll s, ll e, ll l, ll r, ll mn, ll mx){
        if(e < l || s > r) return 0;
        if(l <= s && e <= r){
            ll I = lower_bound(T[node].begin(), T[node].end(), mn) - T[node].begin();
            return (I < T[node].size() && T[node][I] <= mx);
        }
        ll m = (s + e) / 2, lch = node * 2, rch = node * 2 + 1;
        ll x = query(lch, s, m, l, r, mn, mx);
        ll y = query(rch, m + 1, e, l, r, mn, mx);
        return x || y;
    }
private:
    vector<ll> T[2 * S];
};
struct UnionFind{
    ll p[200005];
    UnionFind() {Reset();}
    void Reset() {fill(p, p + 200005, -1);}
    ll Find(ll n) {return (p[n] < 0 ? n : p[n] = Find(p[n]));}
    void Union(ll a, ll b) {a = Find(a), b = Find(b); if(a == b) return; p[a] += p[b]; p[b] = a; }
    bool Same(ll a, ll b) {return Find(a) == Find(b);}
};
UnionFind uf;
 
ll N, M, Q;
vector<ll> G[200005];
ll P1[200005][22];
ll P2[200005][22];
vector<ll> C1[200005];
vector<ll> C2[200005];
ll in1[200005];
ll in2[200005];
ll out1[200005];
ll out2[200005];
ll num1 = 0, num2 = 0;
void ETT1(ll u){
    in1[u] = ++num1;
    for(auto v : C1[u]) ETT1(v);
    out1[u] = num1;
}
void ETT2(ll u){
    in2[u] = ++num2;
    for(auto v : C2[u]) ETT2(v);
    out2[u] = num2;
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
	M = X.size(), Q = S.size();
	vector<int> A(Q);
    for(int i = 0; i < M; i++){
        ll u = ++X[i], v = ++Y[i];
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for(int i = 1; i <= N; i++){
        for(auto j : G[i]){
            if(j > i || uf.Same(i, j)) continue;
            ll k = uf.Find(j);
            uf.Union(i, k);
            P1[k][0] = i;
            C1[i].push_back(k);
        }
    }
    P1[N][0] = N;
    for(int j = 1; j < 22; j++){
        for(int i = 1; i <= N; i++){
            P1[i][j] = P1[P1[i][j - 1]][j - 1]; 
        }
    }
    ETT1(N);
    uf.Reset();
    for(int i = N; i >= 1; i--){
        for(auto j : G[i]){
            if(j < i || uf.Same(i, j)) continue;
            ll k = uf.Find(j);
            uf.Union(i, k);
            P2[k][0] = i;
            C2[i].push_back(k);
        }
    }
    P2[1][0] = 1;
    for(int j = 1; j < 22; j++){
        for(int i = 1; i <= N; i++){
            P2[i][j] = P2[P2[i][j - 1]][j - 1]; 
        }
    }
    ETT2(1);
    MergeSortTree SRT;
    for(int i = 1; i <= N; i++){
        SRT.push(in1[i], in2[i]);
    }
    SRT.init();
    for(int i = 0; i < Q; i++){
        S[i]++, E[i]++, L[i]++, R[i]++;
        ll u = S[i], v = E[i];
        for(int j = 21; j >= 0; j--){
            if(P2[u][j] >= L[i]){
                u = P2[u][j];
            }
        }
        for(int j = 21; j >= 0; j--){
            if(P1[v][j] <= R[i]){
                v = P1[v][j];
            }
        }
        A[i] = SRT.query(in1[v], out1[v], in2[u], out2[u]);
    }
	return A;
}

Compilation message

werewolf.cpp: In member function 'bool MergeSortTree::query(ll, ll, ll, ll, ll, ll, ll)':
werewolf.cpp:24:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |             return (I < T[node].size() && T[node][I] <= mx);
      |                     ~~^~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 65280 KB Output is correct
2 Correct 38 ms 65240 KB Output is correct
3 Correct 39 ms 65240 KB Output is correct
4 Correct 47 ms 65112 KB Output is correct
5 Correct 38 ms 65268 KB Output is correct
6 Correct 39 ms 65356 KB Output is correct
7 Correct 39 ms 65176 KB Output is correct
8 Correct 41 ms 65292 KB Output is correct
9 Correct 38 ms 65244 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 65280 KB Output is correct
2 Correct 38 ms 65240 KB Output is correct
3 Correct 39 ms 65240 KB Output is correct
4 Correct 47 ms 65112 KB Output is correct
5 Correct 38 ms 65268 KB Output is correct
6 Correct 39 ms 65356 KB Output is correct
7 Correct 39 ms 65176 KB Output is correct
8 Correct 41 ms 65292 KB Output is correct
9 Correct 38 ms 65244 KB Output is correct
10 Correct 55 ms 67360 KB Output is correct
11 Correct 45 ms 67428 KB Output is correct
12 Correct 44 ms 67396 KB Output is correct
13 Correct 44 ms 67436 KB Output is correct
14 Correct 44 ms 67396 KB Output is correct
15 Correct 45 ms 67556 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 808 ms 212796 KB Output is correct
2 Correct 1141 ms 214828 KB Output is correct
3 Correct 1048 ms 213480 KB Output is correct
4 Correct 983 ms 212916 KB Output is correct
5 Correct 933 ms 212888 KB Output is correct
6 Correct 894 ms 212784 KB Output is correct
7 Correct 810 ms 212820 KB Output is correct
8 Correct 1098 ms 214852 KB Output is correct
9 Correct 862 ms 213516 KB Output is correct
10 Correct 568 ms 212844 KB Output is correct
11 Correct 666 ms 212784 KB Output is correct
12 Correct 733 ms 212796 KB Output is correct
13 Correct 1123 ms 219572 KB Output is correct
14 Correct 1117 ms 219572 KB Output is correct
15 Correct 1101 ms 219572 KB Output is correct
16 Correct 1066 ms 219584 KB Output is correct
17 Correct 808 ms 212780 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 65280 KB Output is correct
2 Correct 38 ms 65240 KB Output is correct
3 Correct 39 ms 65240 KB Output is correct
4 Correct 47 ms 65112 KB Output is correct
5 Correct 38 ms 65268 KB Output is correct
6 Correct 39 ms 65356 KB Output is correct
7 Correct 39 ms 65176 KB Output is correct
8 Correct 41 ms 65292 KB Output is correct
9 Correct 38 ms 65244 KB Output is correct
10 Correct 55 ms 67360 KB Output is correct
11 Correct 45 ms 67428 KB Output is correct
12 Correct 44 ms 67396 KB Output is correct
13 Correct 44 ms 67436 KB Output is correct
14 Correct 44 ms 67396 KB Output is correct
15 Correct 45 ms 67556 KB Output is correct
16 Correct 808 ms 212796 KB Output is correct
17 Correct 1141 ms 214828 KB Output is correct
18 Correct 1048 ms 213480 KB Output is correct
19 Correct 983 ms 212916 KB Output is correct
20 Correct 933 ms 212888 KB Output is correct
21 Correct 894 ms 212784 KB Output is correct
22 Correct 810 ms 212820 KB Output is correct
23 Correct 1098 ms 214852 KB Output is correct
24 Correct 862 ms 213516 KB Output is correct
25 Correct 568 ms 212844 KB Output is correct
26 Correct 666 ms 212784 KB Output is correct
27 Correct 733 ms 212796 KB Output is correct
28 Correct 1123 ms 219572 KB Output is correct
29 Correct 1117 ms 219572 KB Output is correct
30 Correct 1101 ms 219572 KB Output is correct
31 Correct 1066 ms 219584 KB Output is correct
32 Correct 808 ms 212780 KB Output is correct
33 Correct 1112 ms 214592 KB Output is correct
34 Correct 358 ms 103492 KB Output is correct
35 Correct 1296 ms 216652 KB Output is correct
36 Correct 983 ms 213496 KB Output is correct
37 Correct 1282 ms 215892 KB Output is correct
38 Correct 1048 ms 214248 KB Output is correct
39 Correct 1224 ms 220932 KB Output is correct
40 Correct 1052 ms 227068 KB Output is correct
41 Correct 1002 ms 215504 KB Output is correct
42 Correct 650 ms 213464 KB Output is correct
43 Correct 1414 ms 222140 KB Output is correct
44 Correct 1237 ms 215876 KB Output is correct
45 Correct 960 ms 221308 KB Output is correct
46 Correct 998 ms 220956 KB Output is correct
47 Correct 1075 ms 219892 KB Output is correct
48 Correct 1024 ms 219604 KB Output is correct
49 Correct 1058 ms 219880 KB Output is correct
50 Correct 1044 ms 219536 KB Output is correct
51 Correct 917 ms 226608 KB Output is correct
52 Correct 920 ms 226516 KB Output is correct