oj.uz

Submission #936152

# Submission time Handle Problem Language Result Execution time Memory
936152 2024-03-01T09:30:38 Z GrindMachine Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 106004 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 < n-1 and up2[t][0] <= r){
            t = up2[t][0];
        }

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

    dfs3(0);

    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 36696 KB Output is correct
2 Correct 9 ms 36700 KB Output is correct
3 Correct 9 ms 36952 KB Output is correct
4 Correct 9 ms 36900 KB Output is correct
5 Correct 11 ms 36700 KB Output is correct
6 Correct 9 ms 36700 KB Output is correct
7 Correct 9 ms 36888 KB Output is correct
8 Correct 10 ms 36700 KB Output is correct
9 Correct 10 ms 36900 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 36696 KB Output is correct
2 Correct 9 ms 36700 KB Output is correct
3 Correct 9 ms 36952 KB Output is correct
4 Correct 9 ms 36900 KB Output is correct
5 Correct 11 ms 36700 KB Output is correct
6 Correct 9 ms 36700 KB Output is correct
7 Correct 9 ms 36888 KB Output is correct
8 Correct 10 ms 36700 KB Output is correct
9 Correct 10 ms 36900 KB Output is correct
10 Correct 17 ms 37724 KB Output is correct
11 Correct 17 ms 37680 KB Output is correct
12 Correct 13 ms 37468 KB Output is correct
13 Correct 22 ms 37720 KB Output is correct
14 Correct 23 ms 37724 KB Output is correct
15 Correct 25 ms 37788 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 568 ms 106004 KB Output is correct
2 Execution timed out 4090 ms 104892 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 36696 KB Output is correct
2 Correct 9 ms 36700 KB Output is correct
3 Correct 9 ms 36952 KB Output is correct
4 Correct 9 ms 36900 KB Output is correct
5 Correct 11 ms 36700 KB Output is correct
6 Correct 9 ms 36700 KB Output is correct
7 Correct 9 ms 36888 KB Output is correct
8 Correct 10 ms 36700 KB Output is correct
9 Correct 10 ms 36900 KB Output is correct
10 Correct 17 ms 37724 KB Output is correct
11 Correct 17 ms 37680 KB Output is correct
12 Correct 13 ms 37468 KB Output is correct
13 Correct 22 ms 37720 KB Output is correct
14 Correct 23 ms 37724 KB Output is correct
15 Correct 25 ms 37788 KB Output is correct
16 Correct 568 ms 106004 KB Output is correct
17 Execution timed out 4090 ms 104892 KB Time limit exceeded
18 Halted 0 ms 0 KB -