Submission #750538

#	Time	Username	Problem	Language	Result	Execution time	Memory
750538		GrindMachine	Inside information (BOI21_servers)	C++17	100 / 100	3017 ms	157044 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
some codes

type Q queries:

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

type C queries:
centroid decomp

*/
 
const int MOD = 1e9 + 7;
const int N = 1.2e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
 
 template<typename T>
struct fenwick {
    int siz;
    vector<T> tree;

    fenwick(){

    }

    fenwick(int n) {
        siz = n;
        tree = vector<T>(n + 1);
    }

    int lsb(int x) {
        return x & -x;
    }

    void build(vector<T> &a, int n) {
        for (int i = 1; i <= n; ++i) {
            int par = i + lsb(i);
            tree[i] += a[i];

            if (par <= siz) {
                tree[par] += tree[i];
            }
        }
    }

    void pupd(int i, T v) {
        i++;

        while (i <= siz) {
            tree[i] += v;
            i += lsb(i);
        }
    }

    T sum(int i) {
        i++;

        T res = 0;

        while (i) {
            res += tree[i];
            i -= lsb(i);
        }

        return res;
    }

    T query(int l, int r) {
        if (l > r) return 0;
        T res = sum(r) - sum(l - 1);
        return res;
    }
};

vector<pii> 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;
        } 
    }

    array<int,4> path_data(int u, int v){
        // returns {is_inc, is_dec, mn, mx}
        int lca = query(u,v);
 
        auto [mn1,mx1,inc1,dec1] = get(u,lca);
        auto [mn2,mx2,inc2,dec2] = get(v,lca);
    
        int is_inc = 0, is_dec = 0;

        if(inc1 and dec2 and mx1 < mn2){
            is_inc = 1;
        }

        if(dec1 and inc2 and mn1 > mx2){
            is_dec = 1;
        }

        int mn = min(mn1,mn2);
        int mx = max(mx1,mx2);

        return {is_inc, is_dec, mn, mx};
    }
};

vector<int> subsiz(N), par(N,-1);
vector<bool> rem(N);

int get_siz(int u, int p){
    subsiz[u] = 1;
    for(auto [v, id] : adj[u]){
        if(rem[v] or v == p) conts;
        subsiz[u] += get_siz(v,u);
    }
    return subsiz[u];
}

int get_centroid(int u, int p, int nodes){
    for(auto [v, id] : adj[u]){
        if(rem[v] or v == p) conts;
        if(subsiz[v] > nodes / 2){
            return get_centroid(v,u,nodes);
        }
    }
    return u;
}

void build(int u, int p){
    int nodes = get_siz(u,-1);
    int centroid = get_centroid(u,-1,nodes);

    rem[centroid] = 1;
    par[centroid] = p;

    for(auto [v, id] : adj[centroid]){
        if(rem[v]) conts;
        build(v,centroid);
    }
}

vector<int> adj_ids[N];
fenwick<int> fenw[N];

void solve(int test_case)
{
    int n,k; cin >> n >> k;
    vector<array<int,3>> queries(n+k+5);
 
    rep1(id,n+k-1){
        char ch; cin >> ch;
        int t = 0;
        if(ch == 'S') t = 1;
        else if(ch == 'Q') t = 2;
        else t = 3;
    
        if(t <= 2){
            int u,v; cin >> u >> v;
            queries[id] = {t, u, v};        
            
            if(t == 1){
                adj[u].pb({v,id});
                adj[v].pb({u,id});

                adj_ids[u].pb(id);
                adj_ids[v].pb(id);
            }   
        }
        else{
            int u; cin >> u;
            queries[id] = {t, u};
        }
    }
    
    rep1(i,n){
        adj_ids[i].pb(-inf1);
        adj_ids[i].pb(inf1);
        sort(all(adj_ids[i]));
        int siz = sz(adj_ids[i]);
        fenw[i] = fenwick<int>(siz);
    }

    lca_algo LCA(n);
    build(1,-1);

    vector<pii> here[n+k+5];
    vector<array<int,4>> vals[n+5];

    rep1(u,n){
        for(int centroid = u; centroid != -1; centroid = par[centroid]){
            auto [is_inc, is_dec, mn, mx] = LCA.path_data(u,centroid);
            auto &ids = adj_ids[centroid];
            int mx_ind = lower_bound(all(ids),mx) - ids.begin();
            vals[u].pb({centroid, is_inc, mx, mx_ind});

            if(!is_dec) conts;

            amax(mx, 1);
            mn = lower_bound(all(ids),mn) - ids.begin();
            here[mx].pb({centroid,mn});
        }
    }

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

        for(auto [centroid, pos] : here[id]){
            fenw[centroid].pupd(pos,1);
        }

        if(t == 1) conts;

        if(t == 2){
            if(LCA.is_inc(v,u,id)) yes;
            else no;
            conts;
        }

        int ans = 0;

        for(auto [centroid, is_inc, mx, mx_ind] : vals[u]){
            if(!is_inc) conts;
            if(mx > id) conts;

            int siz = sz(adj_ids[centroid]);
            ans += fenw[centroid].query(mx_ind+1, siz-1);
        }

        cout << ans << endl;
    }
}
 
int main()
{
    fastio;
 
    int t = 1;
    // cin >> t;
 
    rep1(i, t) {
        solve(i);
    }
 
    return 0;
}

Compilation message (stderr)

servers.cpp: In member function 'void lca_algo::lca_dfs(int, int)':
servers.cpp:189:94: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  189 |                 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:190:94: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  190 |                 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:236:58: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  236 |             curr_new[2] = (curr[2] & inc[u][j] & curr[1] < mn[u][j]);
servers.cpp:237:58: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  237 |             curr_new[3] = (curr[3] & dec[u][j] & curr[0] > mx[u][j]);

• Subtask 1: 2.5 / 2.5
• Subtask 2: 2.5 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 2.5 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 12.5 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 17.5 / 17.5