oj.uz

Submission #749526

# Submission time Handle Problem Language Result Execution time Memory
749526 2023-05-28T07:06:56 Z GrindMachine Inside information (BOI21_servers) C++17
50 / 100
 563 ms 93520 KB 
// Om Namah Shivaya

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

/*



*/

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

vector<pll> adj[N];

struct lca_algo {
    // LCA template (for graphs with 1-based indexing)

    int LOG = 1;
    vector<int> depth;
    vector<vector<int>> up;
    vector<vector<int>> mn, mx, inc, dec;

    lca_algo() {

    }

    lca_algo(int n) {
        lca_init(n);
    }

    void lca_init(int n) {
        while ((1 << LOG) < n) LOG++;
        up = vector<vector<int>>(n + 1, vector<int>(LOG, 1));
        depth = vector<int>(n + 1);
        mn = vector<vector<int>>(n + 1, vector<int>(LOG, inf1));
        mx = vector<vector<int>>(n + 1, vector<int>(LOG, -inf1));
        inc = vector<vector<int>>(n + 1, vector<int>(LOG, 1));
        dec = vector<vector<int>>(n + 1, vector<int>(LOG, 1));

        lca_dfs(1, -1);
    }

    void lca_dfs(int node, int par) {
        for(auto [child, w] : adj[node]) {
            if (child == par) conts;

            depth[child] = depth[node] + 1;

            up[child][0] = node;
            rep1(j, LOG - 1) {
                up[child][j] = up[up[child][j - 1]][j - 1];
            }

            mn[child][0] = mx[child][0] = w;
            rep1(j,LOG-1){
                mn[child][j] = min(mn[child][j-1], mn[up[child][j-1]][j-1]);
                mx[child][j] = max(mx[child][j-1], mx[up[child][j-1]][j-1]);
            }

            inc[child][0] = dec[child][0] = 1;
            rep1(j,LOG-1){
                inc[child][j] = (inc[child][j-1] & inc[up[child][j-1]][j-1] & mx[child][j-1] < mn[up[child][j-1]][j-1]);
                dec[child][j] = (dec[child][j-1] & dec[up[child][j-1]][j-1] & mn[child][j-1] > mx[up[child][j-1]][j-1]);
            }

            lca_dfs(child, node);
        }
    }

    int lift(int u, int k) {
        rep(j, LOG) {
            if (k & (1 << j)) {
                u = up[u][j];
            }
        }

        return u;
    }

    int query(int u, int v) {
        if (depth[u] < depth[v]) swap(u, v);
        int k = depth[u] - depth[v];
        u = lift(u, k);

        if (u == v) return u;

        rev(j, LOG - 1, 0) {
            if (up[u][j] != up[v][j]) {
                u = up[u][j];
                v = up[v][j];
            }
        }

        u = up[u][0];
        return u;
    }

    array<int,4> get(int u, int lca){
        int k = depth[u] - depth[lca];
        array<int,4> curr = {inf1,-inf1,1,1};

        rep(j,LOG){
            if(!(k & (1 << j))) conts;

            // merge curr with up[u][j]
            array<int,4> curr_new;
            curr_new[0] = min(curr[0], mn[u][j]);
            curr_new[1] = max(curr[1], mx[u][j]);
            curr_new[2] = (curr[2] & inc[u][j] & curr[1] < mn[u][j]);
            curr_new[3] = (curr[3] & dec[u][j] & curr[0] > mx[u][j]);

            curr = curr_new;
            u = up[u][j];
        }

        assert(u == lca);
        return curr;
    }

    int get_dis(int u, int v) {
        int lca = query(u, v);
        return depth[u] + depth[v] - 2 * depth[lca];
    }
};

void solve(int test_case)
{
    ll n,k; cin >> n >> k;
    vector<array<ll,3>> queries(n+k+5);

    rep1(id,n+k-1){
        char ch; cin >> ch;
        ll t = 0;
        if(ch == 'S') t = 1;
        else if(ch == 'Q') t = 2;
        else t = 3;

        assert(t != 3);

        ll u,v; cin >> u >> v;
        queries[id] = {t, u, v};        
        
        if(t == 1){
            adj[u].pb({v,id});
            adj[v].pb({u,id});
        }
    }

    lca_algo LCA(n);

    rep1(id,n+k-1){
        auto [t,u,v] = queries[id];
        if(t == 1) conts;

        /*

        if val v is contained in node u, then:
        1) the id of the edges on the path from v to u must be increasing (so that v passes through all nodes on the path and eventually comes to u)
        2) and the max edge id on the path must be less than the curr query id (otherwise the max edge will never exist during the time of the query, so u and v will never be connected during the time of the query)

        rewriting the conditions by including the lca so that it's easier to compute:

        v -> u = v -> lca + lca -> u

        v -> lca = inc
        u -> lca = dec
        max(v->lca) < min(u->lca)
        max(v->u) < id
    
        */

        ll lca = LCA.query(u,v);

        auto [mn1,mx1,inc1,dec1] = LCA.get(v,lca);
        auto [mn2,mx2,inc2,dec2] = LCA.get(u,lca);

        if(inc1 and dec2 and mx1 < mn2 and max(mx1,mx2) < id){
            yes;
        }
        else{
            no;
        } 
    }
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Compilation message

servers.cpp: In member function 'void lca_algo::lca_dfs(int, int)':
servers.cpp:111:94: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  111 |                 inc[child][j] = (inc[child][j-1] & inc[up[child][j-1]][j-1] & mx[child][j-1] < mn[up[child][j-1]][j-1]);
servers.cpp:112:94: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  112 |                 dec[child][j] = (dec[child][j-1] & dec[up[child][j-1]][j-1] & mn[child][j-1] > mx[up[child][j-1]][j-1]);
servers.cpp: In member function 'std::array<int, 4> lca_algo::get(int, int)':
servers.cpp:158:58: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  158 |             curr_new[2] = (curr[2] & inc[u][j] & curr[1] < mn[u][j]);
servers.cpp:159:58: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  159 |             curr_new[3] = (curr[3] & dec[u][j] & curr[0] > mx[u][j]);

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 6220 KB Output is correct
2 Correct 49 ms 8268 KB Output is correct
3 Correct 41 ms 8392 KB Output is correct
4 Correct 68 ms 8476 KB Output is correct
5 Correct 64 ms 8712 KB Output is correct
6 Correct 45 ms 8272 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 6220 KB Output is correct
2 Correct 49 ms 8268 KB Output is correct
3 Correct 41 ms 8392 KB Output is correct
4 Correct 68 ms 8476 KB Output is correct
5 Correct 64 ms 8712 KB Output is correct
6 Correct 45 ms 8272 KB Output is correct
7 Runtime error 9 ms 11860 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 6360 KB Output is correct
2 Correct 321 ms 79180 KB Output is correct
3 Correct 345 ms 79160 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 6360 KB Output is correct
2 Correct 321 ms 79180 KB Output is correct
3 Correct 345 ms 79160 KB Output is correct
4 Runtime error 9 ms 11988 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 6224 KB Output is correct
2 Correct 303 ms 90180 KB Output is correct
3 Correct 270 ms 90080 KB Output is correct
4 Correct 324 ms 92756 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 6224 KB Output is correct
2 Correct 303 ms 90180 KB Output is correct
3 Correct 270 ms 90080 KB Output is correct
4 Correct 324 ms 92756 KB Output is correct
5 Runtime error 9 ms 11948 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 6332 KB Output is correct
2 Correct 287 ms 80792 KB Output is correct
3 Correct 263 ms 81104 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 6332 KB Output is correct
2 Correct 287 ms 80792 KB Output is correct
3 Correct 263 ms 81104 KB Output is correct
4 Runtime error 8 ms 11988 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 6224 KB Output is correct
2 Correct 281 ms 90264 KB Output is correct
3 Correct 272 ms 90124 KB Output is correct
4 Correct 349 ms 92748 KB Output is correct
5 Correct 26 ms 7240 KB Output is correct
6 Correct 256 ms 80740 KB Output is correct
7 Correct 248 ms 81064 KB Output is correct
8 Correct 383 ms 81400 KB Output is correct
9 Correct 316 ms 81312 KB Output is correct
10 Correct 395 ms 87332 KB Output is correct
11 Correct 556 ms 86336 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 6224 KB Output is correct
2 Correct 281 ms 90264 KB Output is correct
3 Correct 272 ms 90124 KB Output is correct
4 Correct 349 ms 92748 KB Output is correct
5 Correct 26 ms 7240 KB Output is correct
6 Correct 256 ms 80740 KB Output is correct
7 Correct 248 ms 81064 KB Output is correct
8 Correct 383 ms 81400 KB Output is correct
9 Correct 316 ms 81312 KB Output is correct
10 Correct 395 ms 87332 KB Output is correct
11 Correct 556 ms 86336 KB Output is correct
12 Runtime error 8 ms 11860 KB Execution killed with signal 6
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 6356 KB Output is correct
2 Correct 67 ms 8240 KB Output is correct
3 Correct 41 ms 8420 KB Output is correct
4 Correct 70 ms 8600 KB Output is correct
5 Correct 64 ms 8716 KB Output is correct
6 Correct 44 ms 8288 KB Output is correct
7 Correct 24 ms 6356 KB Output is correct
8 Correct 296 ms 79180 KB Output is correct
9 Correct 300 ms 79180 KB Output is correct
10 Correct 29 ms 7116 KB Output is correct
11 Correct 270 ms 93520 KB Output is correct
12 Correct 262 ms 93488 KB Output is correct
13 Correct 376 ms 92688 KB Output is correct
14 Correct 27 ms 7116 KB Output is correct
15 Correct 252 ms 80844 KB Output is correct
16 Correct 235 ms 81076 KB Output is correct
17 Correct 386 ms 81360 KB Output is correct
18 Correct 320 ms 81304 KB Output is correct
19 Correct 403 ms 87288 KB Output is correct
20 Correct 563 ms 86492 KB Output is correct
21 Correct 320 ms 79716 KB Output is correct
22 Correct 313 ms 79868 KB Output is correct
23 Correct 305 ms 80456 KB Output is correct
24 Correct 311 ms 80592 KB Output is correct
25 Correct 370 ms 83528 KB Output is correct
26 Correct 277 ms 80432 KB Output is correct
27 Correct 242 ms 80280 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 6356 KB Output is correct
2 Correct 67 ms 8240 KB Output is correct
3 Correct 41 ms 8420 KB Output is correct
4 Correct 70 ms 8600 KB Output is correct
5 Correct 64 ms 8716 KB Output is correct
6 Correct 44 ms 8288 KB Output is correct
7 Correct 24 ms 6356 KB Output is correct
8 Correct 296 ms 79180 KB Output is correct
9 Correct 300 ms 79180 KB Output is correct
10 Correct 29 ms 7116 KB Output is correct
11 Correct 270 ms 93520 KB Output is correct
12 Correct 262 ms 93488 KB Output is correct
13 Correct 376 ms 92688 KB Output is correct
14 Correct 27 ms 7116 KB Output is correct
15 Correct 252 ms 80844 KB Output is correct
16 Correct 235 ms 81076 KB Output is correct
17 Correct 386 ms 81360 KB Output is correct
18 Correct 320 ms 81304 KB Output is correct
19 Correct 403 ms 87288 KB Output is correct
20 Correct 563 ms 86492 KB Output is correct
21 Correct 320 ms 79716 KB Output is correct
22 Correct 313 ms 79868 KB Output is correct
23 Correct 305 ms 80456 KB Output is correct
24 Correct 311 ms 80592 KB Output is correct
25 Correct 370 ms 83528 KB Output is correct
26 Correct 277 ms 80432 KB Output is correct
27 Correct 242 ms 80280 KB Output is correct
28 Runtime error 8 ms 11860 KB Execution killed with signal 6
29 Halted 0 ms 0 KB -