oj.uz

Submission #936159

# Submission time Handle Problem Language Result Execution time Memory
936159 2024-03-01T09:47:25 Z GrindMachine Werewolf (IOI18_werewolf) C++17
100 / 100
 599 ms 126976 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

check if there is at least 1 common node in the:
cc of s in the subgraph induced by nodes >= l and
cc of t in the subgraph induced by nodes <= r

key idea:
build a tree s.t any induced subgraph of nodes >= l for a given s forms a connected subtree

how to do this?
add nodes into a dsu in dec ord of indices
let's say u has effective edges to v1,v2,...,vk
connect u to the min value node in each of the components of v1,v2,...,vk

what does the induced subgraph for (s,l) look like?
in the tree, par(u) < u
keep going up from s as long as the node is >= l
let's say we stop at s'
par(s') < l, so we can only visit nodes in the subtree of s'
s' >= l, so everybody in the subtree >= l, so we can indeed visit everyone in the subtree of s'

a similar tree can be built for nodes in inc ord of indices (to calculate (t,r))

check if the subtree of u in tree1 and the subtree of v in tree2 have at least 1 node in common
answer queries offline
run a dfs for both trees and calculate tin,tout times
when at a node u in tree1, find the set of tin2[v] times for all nodes in the subtree of u in tree1
sets can be maintained efficiently using small to large merging
answer all queries at node u:
check if there exists a value x s.t l <= x <= r
=> can be done with set.lower_bound()

*/

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];
        rev(j,LOG-1,0){
            if(up1[s][j] >= l){
                s = up1[s][j];
            }
        }
        rev(j,LOG-1,0){
            if(up2[t][j] <= r){
                t = up2[t][j];
            }
        }

        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 8 ms 36696 KB Output is correct
2 Correct 10 ms 36700 KB Output is correct
3 Correct 9 ms 36884 KB Output is correct
4 Correct 9 ms 36700 KB Output is correct
5 Correct 8 ms 36700 KB Output is correct
6 Correct 9 ms 36700 KB Output is correct
7 Correct 8 ms 36792 KB Output is correct
8 Correct 9 ms 36700 KB Output is correct
9 Correct 9 ms 36700 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 36696 KB Output is correct
2 Correct 10 ms 36700 KB Output is correct
3 Correct 9 ms 36884 KB Output is correct
4 Correct 9 ms 36700 KB Output is correct
5 Correct 8 ms 36700 KB Output is correct
6 Correct 9 ms 36700 KB Output is correct
7 Correct 8 ms 36792 KB Output is correct
8 Correct 9 ms 36700 KB Output is correct
9 Correct 9 ms 36700 KB Output is correct
10 Correct 15 ms 37468 KB Output is correct
11 Correct 13 ms 37468 KB Output is correct
12 Correct 13 ms 37472 KB Output is correct
13 Correct 13 ms 37724 KB Output is correct
14 Correct 15 ms 37720 KB Output is correct
15 Correct 14 ms 37720 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 563 ms 106152 KB Output is correct
2 Correct 441 ms 109572 KB Output is correct
3 Correct 437 ms 105504 KB Output is correct
4 Correct 476 ms 103940 KB Output is correct
5 Correct 464 ms 104192 KB Output is correct
6 Correct 497 ms 106092 KB Output is correct
7 Correct 560 ms 106328 KB Output is correct
8 Correct 382 ms 109572 KB Output is correct
9 Correct 363 ms 105080 KB Output is correct
10 Correct 383 ms 103936 KB Output is correct
11 Correct 400 ms 103596 KB Output is correct
12 Correct 459 ms 103936 KB Output is correct
13 Correct 495 ms 126720 KB Output is correct
14 Correct 547 ms 126688 KB Output is correct
15 Correct 559 ms 126536 KB Output is correct
16 Correct 498 ms 126764 KB Output is correct
17 Correct 552 ms 107264 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 36696 KB Output is correct
2 Correct 10 ms 36700 KB Output is correct
3 Correct 9 ms 36884 KB Output is correct
4 Correct 9 ms 36700 KB Output is correct
5 Correct 8 ms 36700 KB Output is correct
6 Correct 9 ms 36700 KB Output is correct
7 Correct 8 ms 36792 KB Output is correct
8 Correct 9 ms 36700 KB Output is correct
9 Correct 9 ms 36700 KB Output is correct
10 Correct 15 ms 37468 KB Output is correct
11 Correct 13 ms 37468 KB Output is correct
12 Correct 13 ms 37472 KB Output is correct
13 Correct 13 ms 37724 KB Output is correct
14 Correct 15 ms 37720 KB Output is correct
15 Correct 14 ms 37720 KB Output is correct
16 Correct 563 ms 106152 KB Output is correct
17 Correct 441 ms 109572 KB Output is correct
18 Correct 437 ms 105504 KB Output is correct
19 Correct 476 ms 103940 KB Output is correct
20 Correct 464 ms 104192 KB Output is correct
21 Correct 497 ms 106092 KB Output is correct
22 Correct 560 ms 106328 KB Output is correct
23 Correct 382 ms 109572 KB Output is correct
24 Correct 363 ms 105080 KB Output is correct
25 Correct 383 ms 103936 KB Output is correct
26 Correct 400 ms 103596 KB Output is correct
27 Correct 459 ms 103936 KB Output is correct
28 Correct 495 ms 126720 KB Output is correct
29 Correct 547 ms 126688 KB Output is correct
30 Correct 559 ms 126536 KB Output is correct
31 Correct 498 ms 126764 KB Output is correct
32 Correct 552 ms 107264 KB Output is correct
33 Correct 599 ms 106304 KB Output is correct
34 Correct 180 ms 60556 KB Output is correct
35 Correct 546 ms 112824 KB Output is correct
36 Correct 541 ms 106220 KB Output is correct
37 Correct 554 ms 111356 KB Output is correct
38 Correct 533 ms 107520 KB Output is correct
39 Correct 589 ms 121636 KB Output is correct
40 Correct 543 ms 118920 KB Output is correct
41 Correct 471 ms 109052 KB Output is correct
42 Correct 455 ms 104704 KB Output is correct
43 Correct 553 ms 119644 KB Output is correct
44 Correct 496 ms 110848 KB Output is correct
45 Correct 470 ms 120536 KB Output is correct
46 Correct 532 ms 120496 KB Output is correct
47 Correct 555 ms 126892 KB Output is correct
48 Correct 509 ms 126748 KB Output is correct
49 Correct 497 ms 126696 KB Output is correct
50 Correct 534 ms 126976 KB Output is correct
51 Correct 524 ms 118992 KB Output is correct
52 Correct 510 ms 118528 KB Output is correct