제출 #750419

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
750419		GrindMachine	Inside information (BOI21_servers)	C++17	50 / 100	568 ms	93584 KiB

servers

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

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 0 / 5
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 0 / 17.5