oj.uz

Submission #534460

# Submission time Handle Problem Language Result Execution time Memory
534460 2022-03-08T07:27:40 Z tranxuanbach Inside information (BOI21_servers) C++17
100 / 100
 896 ms 59436 KB 
#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

# Verdict Execution time Memory Grader output
1 Correct 34 ms 14452 KB Output is correct
2 Correct 49 ms 15152 KB Output is correct
3 Correct 57 ms 15316 KB Output is correct
4 Correct 71 ms 15324 KB Output is correct
5 Correct 52 ms 15504 KB Output is correct
6 Correct 53 ms 15020 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 14452 KB Output is correct
2 Correct 49 ms 15152 KB Output is correct
3 Correct 57 ms 15316 KB Output is correct
4 Correct 71 ms 15324 KB Output is correct
5 Correct 52 ms 15504 KB Output is correct
6 Correct 53 ms 15020 KB Output is correct
7 Correct 37 ms 14548 KB Output is correct
8 Correct 70 ms 16960 KB Output is correct
9 Correct 57 ms 17044 KB Output is correct
10 Correct 98 ms 19020 KB Output is correct
11 Correct 110 ms 19364 KB Output is correct
12 Correct 49 ms 16532 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 14596 KB Output is correct
2 Correct 182 ms 31288 KB Output is correct
3 Correct 206 ms 31280 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 14596 KB Output is correct
2 Correct 182 ms 31288 KB Output is correct
3 Correct 206 ms 31280 KB Output is correct
4 Correct 37 ms 14548 KB Output is correct
5 Correct 180 ms 31540 KB Output is correct
6 Correct 206 ms 31664 KB Output is correct
7 Correct 193 ms 31776 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 14460 KB Output is correct
2 Correct 698 ms 48368 KB Output is correct
3 Correct 726 ms 48356 KB Output is correct
4 Correct 589 ms 47156 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 14460 KB Output is correct
2 Correct 698 ms 48368 KB Output is correct
3 Correct 726 ms 48356 KB Output is correct
4 Correct 589 ms 47156 KB Output is correct
5 Correct 35 ms 14552 KB Output is correct
6 Correct 822 ms 56560 KB Output is correct
7 Correct 625 ms 55944 KB Output is correct
8 Correct 896 ms 59412 KB Output is correct
9 Correct 753 ms 59436 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 14624 KB Output is correct
2 Correct 474 ms 37676 KB Output is correct
3 Correct 524 ms 38160 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 14624 KB Output is correct
2 Correct 474 ms 37676 KB Output is correct
3 Correct 524 ms 38160 KB Output is correct
4 Correct 47 ms 14656 KB Output is correct
5 Correct 604 ms 46384 KB Output is correct
6 Correct 600 ms 46544 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 14456 KB Output is correct
2 Correct 603 ms 48348 KB Output is correct
3 Correct 670 ms 48360 KB Output is correct
4 Correct 490 ms 47140 KB Output is correct
5 Correct 31 ms 14604 KB Output is correct
6 Correct 433 ms 37728 KB Output is correct
7 Correct 519 ms 38144 KB Output is correct
8 Correct 535 ms 37340 KB Output is correct
9 Correct 517 ms 37360 KB Output is correct
10 Correct 631 ms 43224 KB Output is correct
11 Correct 661 ms 41944 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 14456 KB Output is correct
2 Correct 603 ms 48348 KB Output is correct
3 Correct 670 ms 48360 KB Output is correct
4 Correct 490 ms 47140 KB Output is correct
5 Correct 31 ms 14604 KB Output is correct
6 Correct 433 ms 37728 KB Output is correct
7 Correct 519 ms 38144 KB Output is correct
8 Correct 535 ms 37340 KB Output is correct
9 Correct 517 ms 37360 KB Output is correct
10 Correct 631 ms 43224 KB Output is correct
11 Correct 661 ms 41944 KB Output is correct
12 Correct 35 ms 14664 KB Output is correct
13 Correct 678 ms 56596 KB Output is correct
14 Correct 537 ms 55912 KB Output is correct
15 Correct 711 ms 59404 KB Output is correct
16 Correct 779 ms 59388 KB Output is correct
17 Correct 35 ms 15420 KB Output is correct
18 Correct 498 ms 46352 KB Output is correct
19 Correct 610 ms 46672 KB Output is correct
20 Correct 626 ms 45716 KB Output is correct
21 Correct 659 ms 45932 KB Output is correct
22 Correct 824 ms 53060 KB Output is correct
23 Correct 864 ms 51584 KB Output is correct
24 Correct 788 ms 47788 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 14452 KB Output is correct
2 Correct 45 ms 15164 KB Output is correct
3 Correct 41 ms 15328 KB Output is correct
4 Correct 49 ms 15296 KB Output is correct
5 Correct 55 ms 15488 KB Output is correct
6 Correct 47 ms 15052 KB Output is correct
7 Correct 38 ms 14552 KB Output is correct
8 Correct 148 ms 31408 KB Output is correct
9 Correct 175 ms 31400 KB Output is correct
10 Correct 39 ms 14532 KB Output is correct
11 Correct 567 ms 48308 KB Output is correct
12 Correct 587 ms 48372 KB Output is correct
13 Correct 498 ms 47140 KB Output is correct
14 Correct 30 ms 14540 KB Output is correct
15 Correct 461 ms 37672 KB Output is correct
16 Correct 508 ms 38152 KB Output is correct
17 Correct 487 ms 37432 KB Output is correct
18 Correct 551 ms 37312 KB Output is correct
19 Correct 642 ms 43340 KB Output is correct
20 Correct 640 ms 41964 KB Output is correct
21 Correct 208 ms 34156 KB Output is correct
22 Correct 183 ms 33404 KB Output is correct
23 Correct 424 ms 37276 KB Output is correct
24 Correct 354 ms 36996 KB Output is correct
25 Correct 583 ms 42832 KB Output is correct
26 Correct 504 ms 36056 KB Output is correct
27 Correct 480 ms 36336 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 14452 KB Output is correct
2 Correct 45 ms 15164 KB Output is correct
3 Correct 41 ms 15328 KB Output is correct
4 Correct 49 ms 15296 KB Output is correct
5 Correct 55 ms 15488 KB Output is correct
6 Correct 47 ms 15052 KB Output is correct
7 Correct 38 ms 14552 KB Output is correct
8 Correct 148 ms 31408 KB Output is correct
9 Correct 175 ms 31400 KB Output is correct
10 Correct 39 ms 14532 KB Output is correct
11 Correct 567 ms 48308 KB Output is correct
12 Correct 587 ms 48372 KB Output is correct
13 Correct 498 ms 47140 KB Output is correct
14 Correct 30 ms 14540 KB Output is correct
15 Correct 461 ms 37672 KB Output is correct
16 Correct 508 ms 38152 KB Output is correct
17 Correct 487 ms 37432 KB Output is correct
18 Correct 551 ms 37312 KB Output is correct
19 Correct 642 ms 43340 KB Output is correct
20 Correct 640 ms 41964 KB Output is correct
21 Correct 208 ms 34156 KB Output is correct
22 Correct 183 ms 33404 KB Output is correct
23 Correct 424 ms 37276 KB Output is correct
24 Correct 354 ms 36996 KB Output is correct
25 Correct 583 ms 42832 KB Output is correct
26 Correct 504 ms 36056 KB Output is correct
27 Correct 480 ms 36336 KB Output is correct
28 Correct 37 ms 14632 KB Output is correct
29 Correct 63 ms 16956 KB Output is correct
30 Correct 56 ms 17080 KB Output is correct
31 Correct 78 ms 19064 KB Output is correct
32 Correct 95 ms 19400 KB Output is correct
33 Correct 44 ms 16432 KB Output is correct
34 Correct 32 ms 15340 KB Output is correct
35 Correct 166 ms 34340 KB Output is correct
36 Correct 172 ms 33288 KB Output is correct
37 Correct 181 ms 33720 KB Output is correct
38 Correct 32 ms 15492 KB Output is correct
39 Correct 723 ms 56592 KB Output is correct
40 Correct 597 ms 55952 KB Output is correct
41 Correct 731 ms 59404 KB Output is correct
42 Correct 770 ms 59388 KB Output is correct
43 Correct 48 ms 15500 KB Output is correct
44 Correct 541 ms 46344 KB Output is correct
45 Correct 658 ms 46640 KB Output is correct
46 Correct 599 ms 45708 KB Output is correct
47 Correct 622 ms 45884 KB Output is correct
48 Correct 775 ms 53080 KB Output is correct
49 Correct 828 ms 51592 KB Output is correct
50 Correct 841 ms 47828 KB Output is correct
51 Correct 212 ms 37556 KB Output is correct
52 Correct 175 ms 34760 KB Output is correct
53 Correct 206 ms 34088 KB Output is correct
54 Correct 173 ms 34468 KB Output is correct
55 Correct 218 ms 37504 KB Output is correct
56 Correct 460 ms 42160 KB Output is correct
57 Correct 588 ms 49096 KB Output is correct
58 Correct 611 ms 45952 KB Output is correct
59 Correct 462 ms 40004 KB Output is correct