Submission #516193

#	Time	Username	Problem	Language	Result	Execution time	Memory
516193		pokmui9909	Werewolf (IOI18_werewolf)	C++17	100 / 100	1414 ms	227068 KiB

werewolf

#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 (stderr)

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 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51