oj.uz

Submission #936151

# Submission time Handle Problem Language Result Execution time Memory
936151 2024-03-01T09:29:43 Z GrindMachine Werewolf (IOI18_werewolf) C++17
0 / 100
 4000 ms 98772 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

refs:
edi

*/

const int MOD = 1e9 + 7;
const int N = 2e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
const int LOG = 18;

#include "werewolf.h"

struct DSU {
    vector<int> par, rankk, siz, mn, mx;

    DSU() {

    }

    DSU(int n) {
        init(n);
    }

    void init(int n) {
        par = vector<int>(n + 1);
        rankk = vector<int>(n + 1);
        siz = vector<int>(n + 1);
        mn = vector<int>(n + 1);
        mx = vector<int>(n + 1);
        rep(i, n + 1) create(i);
    }

    void create(int u) {
        par[u] = u;
        rankk[u] = 0;
        siz[u] = 1;
        mn[u] = u;
        mx[u] = u;
    }

    int find(int u) {
        if (u == par[u]) return u;
        else return par[u] = find(par[u]);
    }

    bool same(int u, int v) {
        return find(u) == find(v);
    }

    void merge(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return;

        if (rankk[u] == rankk[v]) rankk[u]++;
        if (rankk[u] < rankk[v]) swap(u, v);

        par[v] = u;
        siz[u] += siz[v];
        amin(mn[u],mn[v]);
        amax(mx[u],mx[v]);
    }
};

vector<int> adjg[N], adj1[N], adj2[N];
vector<int> tin1(N), tout1(N), subsiz1(N);
vector<int> tin2(N), tout2(N), subsiz2(N);
int up1[N][LOG], up2[N][LOG];
int timer;

void dfs1(int u){
    tin1[u] = timer++;
    subsiz1[u] = 1;
    trav(v,adj1[u]){
        up1[v][0] = u;
        rep1(j,LOG-1){
            up1[v][j] = up1[up1[v][j-1]][j-1];
        }
        dfs1(v);
        subsiz1[u] += subsiz1[v];
    }
    tout1[u] = timer++;
}

void dfs2(int u){
    tin2[u] = timer++;
    subsiz2[u] = 1;
    trav(v,adj2[u]){
        up2[v][0] = u;
        rep1(j,LOG-1){
            up2[v][j] = up2[up2[v][j-1]][j-1];
        }
        dfs2(v);
        subsiz2[u] += subsiz2[v];
    }
    tout2[u] = timer++;
}

set<ll> st[N];
vector<array<int,3>> queries_here[N];
vector<int> ans;

void dfs3(int u){
    pii big = {-1,-1};
    trav(v,adj1[u]){
        pii px = {subsiz1[v],v};
        amax(big,px);
    }

    int heavy = big.ss;
    if(heavy != -1){
        dfs3(heavy);
        swap(st[u],st[heavy]);
    }

    trav(v,adj1[u]){
        if(v == heavy) conts;
        dfs3(v);
        trav(x,st[v]){
            st[u].insert(x);
        }
        st[v].clear();
    }

    st[u].insert(tin2[u]);

    for(auto [l,r,id] : queries_here[u]){
        auto it = st[u].lower_bound(l);
        if(it != st[u].end()){
            if(*it <= r){
                ans[id] = 1;
            }
        }
    }
}

std::vector<int> check_validity(int n, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> T,
                                std::vector<int> L, std::vector<int> R) {

    int m = sz(X), q = sz(S);
    rep(i,m){
        int u = X[i], v = Y[i];
        adjg[u].pb(v), adjg[v].pb(u);
    }

    DSU dsu(n);

    rev(u,n-1,0){
        trav(v,adjg[u]){
            if(u <= v){
                if(!dsu.same(u,v)){
                    int cc = dsu.find(v);
                    int mn = dsu.mn[cc];
                    adj1[u].pb(mn);
                    dsu.merge(u,v);
                }
            }
        }
    }

    dsu = DSU(n);

    rep(u,n){
        trav(v,adjg[u]){
            if(u >= v){
                if(!dsu.same(u,v)){
                    int cc = dsu.find(v);
                    int mx = dsu.mx[cc];
                    adj2[u].pb(mx);
                    dsu.merge(u,v);
                }
            }
        }
    }

    rep(j,LOG) up1[0][j] = 0;
    timer = 1;
    dfs1(0);

    rep(j,LOG) up2[n-1][j] = n-1;
    timer = 1;
    dfs2(n-1);

    ans = vector<int>(q);

    rep(i,q){
        int s = S[i], t = T[i], l = L[i], r = R[i];
        while(s and up1[s][0] >= l){
            s = up1[s][0];
        }
        while(t and up2[t][0] <= r){
            t = up2[t][0];
        }

        queries_here[s].pb({tin2[t],tout2[t],i});
    }

    dfs3(0);

    return ans;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4016 ms 36696 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4016 ms 36696 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4019 ms 98772 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4016 ms 36696 KB Time limit exceeded
2 Halted 0 ms 0 KB -