oj.uz

Submission #750419

# Submission time Handle Problem Language Result Execution time Memory
750419 2023-05-29T13:36:12 Z GrindMachine Inside information (BOI21_servers) C++17
50 / 100
 568 ms 93584 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
 
/*

refs:
edi

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

 
*/
 
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];
    }

    bool is_inc(int u, int v, int t){
        // is the path from u to v increasing at time t?
        int lca = query(u,v);
 
        auto [mn1,mx1,inc1,dec1] = get(u,lca);
        auto [mn2,mx2,inc2,dec2] = get(v,lca);
 
        if(inc1 and dec2 and mx1 < mn2 and max(mx1,mx2) < t){
            return true;
        }
        else{
            return false;
        } 
    }
};
 
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;
    
        if(t <= 2){
            ll u,v; cin >> u >> v;
            queries[id] = {t, u, v};        
            
            if(t == 1){
                adj[u].pb({v,id});
                adj[v].pb({u,id});
            }   
        }
        else{
            ll u; cin >> u;
            queries[id] = {t, u};
        }
    }
 
    lca_algo LCA(n);
 
    rep1(id,n+k-1){
        auto [t,u,v] = queries[id];
        if(t == 1) conts;

        if(LCA.is_inc(v,u,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:126:94: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  126 |                 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:127:94: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  127 |                 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:173:58: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  173 |             curr_new[2] = (curr[2] & inc[u][j] & curr[1] < mn[u][j]);
servers.cpp:174:58: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  174 |             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 31 ms 7108 KB Output is correct
2 Correct 53 ms 9712 KB Output is correct
3 Correct 45 ms 9784 KB Output is correct
4 Correct 71 ms 9816 KB Output is correct
5 Correct 58 ms 10164 KB Output is correct
6 Correct 41 ms 9676 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 7108 KB Output is correct
2 Correct 53 ms 9712 KB Output is correct
3 Correct 45 ms 9784 KB Output is correct
4 Correct 71 ms 9816 KB Output is correct
5 Correct 58 ms 10164 KB Output is correct
6 Correct 41 ms 9676 KB Output is correct
7 Runtime error 31 ms 12716 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 28 ms 7224 KB Output is correct
2 Correct 300 ms 79200 KB Output is correct
3 Correct 319 ms 79192 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 7224 KB Output is correct
2 Correct 300 ms 79200 KB Output is correct
3 Correct 319 ms 79192 KB Output is correct
4 Runtime error 22 ms 12756 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 39 ms 7220 KB Output is correct
2 Correct 316 ms 93584 KB Output is correct
3 Correct 286 ms 93396 KB Output is correct
4 Correct 364 ms 92784 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 7220 KB Output is correct
2 Correct 316 ms 93584 KB Output is correct
3 Correct 286 ms 93396 KB Output is correct
4 Correct 364 ms 92784 KB Output is correct
5 Runtime error 33 ms 12748 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 29 ms 7204 KB Output is correct
2 Correct 262 ms 80748 KB Output is correct
3 Correct 243 ms 81124 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 7204 KB Output is correct
2 Correct 262 ms 80748 KB Output is correct
3 Correct 243 ms 81124 KB Output is correct
4 Runtime error 25 ms 12748 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 44 ms 7216 KB Output is correct
2 Correct 288 ms 93392 KB Output is correct
3 Correct 277 ms 93412 KB Output is correct
4 Correct 359 ms 92736 KB Output is correct
5 Correct 30 ms 7236 KB Output is correct
6 Correct 253 ms 80912 KB Output is correct
7 Correct 251 ms 81100 KB Output is correct
8 Correct 392 ms 81384 KB Output is correct
9 Correct 330 ms 81348 KB Output is correct
10 Correct 416 ms 87312 KB Output is correct
11 Correct 568 ms 86408 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 7216 KB Output is correct
2 Correct 288 ms 93392 KB Output is correct
3 Correct 277 ms 93412 KB Output is correct
4 Correct 359 ms 92736 KB Output is correct
5 Correct 30 ms 7236 KB Output is correct
6 Correct 253 ms 80912 KB Output is correct
7 Correct 251 ms 81100 KB Output is correct
8 Correct 392 ms 81384 KB Output is correct
9 Correct 330 ms 81348 KB Output is correct
10 Correct 416 ms 87312 KB Output is correct
11 Correct 568 ms 86408 KB Output is correct
12 Runtime error 22 ms 12720 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 28 ms 7120 KB Output is correct
2 Correct 51 ms 9728 KB Output is correct
3 Correct 39 ms 9708 KB Output is correct
4 Correct 78 ms 9808 KB Output is correct
5 Correct 62 ms 10092 KB Output is correct
6 Correct 39 ms 9688 KB Output is correct
7 Correct 25 ms 7228 KB Output is correct
8 Correct 307 ms 79220 KB Output is correct
9 Correct 306 ms 79216 KB Output is correct
10 Correct 32 ms 7116 KB Output is correct
11 Correct 266 ms 93500 KB Output is correct
12 Correct 274 ms 93412 KB Output is correct
13 Correct 338 ms 92892 KB Output is correct
14 Correct 26 ms 7116 KB Output is correct
15 Correct 323 ms 80816 KB Output is correct
16 Correct 244 ms 81076 KB Output is correct
17 Correct 379 ms 81416 KB Output is correct
18 Correct 355 ms 81432 KB Output is correct
19 Correct 396 ms 87372 KB Output is correct
20 Correct 550 ms 86392 KB Output is correct
21 Correct 324 ms 79716 KB Output is correct
22 Correct 315 ms 79732 KB Output is correct
23 Correct 314 ms 80376 KB Output is correct
24 Correct 324 ms 80572 KB Output is correct
25 Correct 379 ms 83628 KB Output is correct
26 Correct 285 ms 80284 KB Output is correct
27 Correct 268 ms 80260 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 7120 KB Output is correct
2 Correct 51 ms 9728 KB Output is correct
3 Correct 39 ms 9708 KB Output is correct
4 Correct 78 ms 9808 KB Output is correct
5 Correct 62 ms 10092 KB Output is correct
6 Correct 39 ms 9688 KB Output is correct
7 Correct 25 ms 7228 KB Output is correct
8 Correct 307 ms 79220 KB Output is correct
9 Correct 306 ms 79216 KB Output is correct
10 Correct 32 ms 7116 KB Output is correct
11 Correct 266 ms 93500 KB Output is correct
12 Correct 274 ms 93412 KB Output is correct
13 Correct 338 ms 92892 KB Output is correct
14 Correct 26 ms 7116 KB Output is correct
15 Correct 323 ms 80816 KB Output is correct
16 Correct 244 ms 81076 KB Output is correct
17 Correct 379 ms 81416 KB Output is correct
18 Correct 355 ms 81432 KB Output is correct
19 Correct 396 ms 87372 KB Output is correct
20 Correct 550 ms 86392 KB Output is correct
21 Correct 324 ms 79716 KB Output is correct
22 Correct 315 ms 79732 KB Output is correct
23 Correct 314 ms 80376 KB Output is correct
24 Correct 324 ms 80572 KB Output is correct
25 Correct 379 ms 83628 KB Output is correct
26 Correct 285 ms 80284 KB Output is correct
27 Correct 268 ms 80260 KB Output is correct
28 Runtime error 22 ms 12876 KB Execution killed with signal 6
29 Halted 0 ms 0 KB -