Submission #534460

#	Time	Username	Problem	Language	Result	Execution time	Memory
534460		tranxuanbach	Inside information (BOI21_servers)	C++17	100 / 100	896 ms	59436 KiB

servers

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

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;

template <class T>
using ordered_multiset = tree <T, null_type, less_equal <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 1e5 + 2e4 + 5, Q = 2 * N;

struct query_t{
    char type;
    int u, v;

    query_t(){

    }

    query_t(char type, int u, int v = 0): type(type), u(u), v(v){

    }

    friend istream& operator>> (istream& in, query_t& rhs){
        in >> rhs.type;
        if (rhs.type == 'S'){
            in >> rhs.u >> rhs.v;
        }
        else if (rhs.type == 'Q'){
            in >> rhs.v >> rhs.u;
        }
        else{
            in >> rhs.u;
        }
        return in;
    }

    friend ostream& operator<< (ostream& out, const query_t& rhs){
        out << rhs.type << ' ';
        if (rhs.type == 'S'){
            out << rhs.u << ' ' << rhs.v;
        }
        else if (rhs.type == 'Q'){
            out << rhs.v << ' ' << rhs.u;
        }
        else{
            out << rhs.u;
        }
        return out;
    }
};

int n, q;
query_t a[Q];

vpii adj[N];

int par[N], sz[N];

int ctall;
vi adjct[N];
int parct[N], hct[N];

bool block[N];

void dfs_cpn_ct(int u){
    sz[u] = 1;
    Fora(&edge, adj[u]){
        int v = edge.fi;
        if (v == par[u] or block[v]){
            continue;
        }
        par[v] = u;
        dfs_cpn_ct(v);
        sz[u] += sz[v];
    }
}

int dfs_ct(int u){
    par[u] = 0;
    dfs_cpn_ct(u);
    if (sz[u] == 1){
        return u;
    }
    int sz_cpn = sz[u];
    while (1){
        int v = 0;
        Fora(&edge, adj[u]){
            int tv = edge.fi;
            if (tv == par[u] or block[tv]){
                continue;
            }
            if (sz[tv] * 2 > sz_cpn){
                v = tv;
                break;
            }
        }
        if (v == 0){
            break;
        }
        u = v;
    }
    block[u] = 1;
    Fora(&edge, adj[u]){
        int v = edge.fi;
        if (block[v]){
            continue;
        }
        v = dfs_ct(v);
        adjct[u].emplace_back(v);
        parct[v] = u;
    }
    return u;
}

void dfs_hct(int u){
    Fora(v, adjct[u]){
        hct[v] = hct[u] + 1;
        dfs_hct(v);
    }
}

vi vqueryq[N], vqueryc[N];
int ans[Q];

vi vcpn;
pii pathup[N], pathdown[N];

void dfs_cpn_query(int u){
    vcpn.emplace_back(u);
    Fora(&edge, adj[u]){
        int v = edge.fi, w = edge.se;
        if (v == par[u] or block[v]){
            continue;
        }
        par[v] = u;
        if (pathup[u].fi == Q){
            pathup[v] = make_pair(w, w);
        }
        else if (w < pathup[u].fi){
            pathup[v] = make_pair(w, pathup[u].se);
        }
        else{
            pathup[v] = make_pair(-1, Q + 1);
        }
        if (pathdown[u].fi == Q){
            pathdown[v] = make_pair(w, w);
        }
        else if (w > pathdown[u].se){
            pathdown[v] = make_pair(pathdown[u].fi, w);
        }
        else{
            pathdown[v] = make_pair(-1, Q + 1);
        }
        dfs_cpn_query(v);
    }
}

void dfs_query(int ct){
    par[ct] = 0;
    vcpn.clear();
    pathup[ct] = make_pair(Q, 0);
    pathdown[ct] = make_pair(Q, 0);
    dfs_cpn_query(ct);

    Fora(idx, vqueryq[ct]){
        int u = a[idx].u, v = a[idx].v;
        if (u == ct and v == ct){
            ans[idx] = 1;
        }
        else if (u == ct){
            ans[idx] = (pathdown[v].se < idx);
        }
        else if (v == ct){
            ans[idx] = (pathup[u].se < idx);
        }
        else{
            ans[idx] = (pathup[u].se < pathdown[v].fi and pathdown[v].se < idx);
        }
    }
    vcpn.erase(vcpn.begin());
    Fora(i, vqueryc[ct]){
        if (pathup[a[i].u].se < i){
            ans[i]++;
        }
    }
    sort(bend(vqueryc[ct]), [&](int lhs, int rhs){
        return pathup[a[lhs].u].se > pathup[a[rhs].u].se;
    });
    sort(bend(vcpn), [&](int lhs, int rhs){
        return pathdown[lhs].fi > pathdown[rhs].fi;
    });
    ordered_multiset <int> stt;
    int ctrvqueryc = 0, ctrvcpn = 0;
    while (ctrvqueryc < isz(vqueryc[ct]) or ctrvcpn < isz(vcpn)){
        if (ctrvqueryc == isz(vqueryc[ct])){
            stt.insert(pathdown[vcpn[ctrvcpn]].se);
            ctrvcpn++;
            continue;
        }
        if (ctrvcpn == isz(vcpn)){
            ans[vqueryc[ct][ctrvqueryc]] += stt.order_of_key(vqueryc[ct][ctrvqueryc]);
            ctrvqueryc++;
            continue;
        }
        if (pathdown[vcpn[ctrvcpn]].fi > pathup[a[vqueryc[ct][ctrvqueryc]].u].se){
            stt.insert(pathdown[vcpn[ctrvcpn]].se);
            ctrvcpn++;
            continue;
        }
        else{
            ans[vqueryc[ct][ctrvqueryc]] += stt.order_of_key(vqueryc[ct][ctrvqueryc]);
            ctrvqueryc++;
            continue;
        }
    }

    block[ct] = 1;
    Fora(vct, adjct[ct]){
        dfs_query(vct);
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("KEK.inp", "r", stdin);
    // freopen("KEK.out", "w", stdout);
    {
        cin >> n >> q;
        q += n - 1;
        ForE(i, 1, q){
            cin >> a[i];
        }
    }

    ForE(i, 1, q){
        if (a[i].type == 'S'){
            adj[a[i].u].emplace_back(a[i].v, i);
            adj[a[i].v].emplace_back(a[i].u, i);
        }
    }

    memset(block, 0, sizeof(block));
    ctall = dfs_ct(1);
    dfs_hct(ctall);

    ForE(i, 1, q){
        if (a[i].type == 'Q'){
            int u = a[i].u, v = a[i].v;
            if (hct[u] < hct[v]){
                swap(u, v);
            }
            while (hct[u] > hct[v]){
                u = parct[u];
            }
            while (u != v){
                u = parct[u]; v = parct[v];
            }
            vqueryq[u].emplace_back(i);
        }
        else if (a[i].type == 'C'){
            int u = a[i].u;
            while (u != ctall){
                vqueryc[u].emplace_back(i);
                u = parct[u];
            }
            vqueryc[u].emplace_back(i);
        }
    }

    memset(block, 0, sizeof(block));
    dfs_query(ctall);
    ForE(i, 1, q){
        if (a[i].type == 'Q'){
            if (ans[i]){
                cout << "yes" << endl;
            }
            else{
                cout << "no" << endl;
            }
        }
        else if (a[i].type == 'C'){
            cout << ans[i] << endl;
        }
    }
}

/*
==================================================+
INPUT:                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

• 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