oj.uz

Submission #534428

# Submission time Handle Problem Language Result Execution time Memory
534428 2022-03-08T07:00:39 Z tranxuanbach Inside information (BOI21_servers) C++17
50 / 100
 650 ms 49440 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, N2 = 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 >> rhs.u;
        if (rhs.type != 'C'){
            in >> rhs.v;
        }
        return in;
    }
};

int n, q;
query_t a[N2];

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[N2];

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 == N2){
            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, N2 + 1);
        }
        if (pathdown[u].fi == N2){
            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, N2 + 1);
        }
        dfs_cpn_query(v);
    }
}

void dfs_query(int ct){
    par[ct] = 0;
    vcpn.clear();
    pathup[ct] = make_pair(N2, 0);
    pathdown[ct] = make_pair(N2, 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);
        }
    }
    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'){
            swap(a[i].u, a[i].v);
            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 36 ms 15236 KB Output is correct
2 Correct 56 ms 16144 KB Output is correct
3 Correct 61 ms 16312 KB Output is correct
4 Correct 69 ms 16396 KB Output is correct
5 Correct 66 ms 16520 KB Output is correct
6 Correct 53 ms 16012 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 15236 KB Output is correct
2 Correct 56 ms 16144 KB Output is correct
3 Correct 61 ms 16312 KB Output is correct
4 Correct 69 ms 16396 KB Output is correct
5 Correct 66 ms 16520 KB Output is correct
6 Correct 53 ms 16012 KB Output is correct
7 Incorrect 42 ms 15316 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 15360 KB Output is correct
2 Correct 240 ms 32388 KB Output is correct
3 Correct 186 ms 32396 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 15360 KB Output is correct
2 Correct 240 ms 32388 KB Output is correct
3 Correct 186 ms 32396 KB Output is correct
4 Incorrect 33 ms 15184 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 15216 KB Output is correct
2 Correct 638 ms 49400 KB Output is correct
3 Correct 605 ms 49400 KB Output is correct
4 Correct 447 ms 48184 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 15216 KB Output is correct
2 Correct 638 ms 49400 KB Output is correct
3 Correct 605 ms 49400 KB Output is correct
4 Correct 447 ms 48184 KB Output is correct
5 Incorrect 36 ms 15216 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 15268 KB Output is correct
2 Correct 444 ms 38772 KB Output is correct
3 Correct 530 ms 39320 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 15268 KB Output is correct
2 Correct 444 ms 38772 KB Output is correct
3 Correct 530 ms 39320 KB Output is correct
4 Incorrect 32 ms 15420 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 15196 KB Output is correct
2 Correct 583 ms 49440 KB Output is correct
3 Correct 585 ms 49428 KB Output is correct
4 Correct 450 ms 48184 KB Output is correct
5 Correct 31 ms 15268 KB Output is correct
6 Correct 417 ms 38780 KB Output is correct
7 Correct 487 ms 39356 KB Output is correct
8 Correct 509 ms 38408 KB Output is correct
9 Correct 510 ms 38552 KB Output is correct
10 Correct 625 ms 44360 KB Output is correct
11 Correct 626 ms 42988 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 15196 KB Output is correct
2 Correct 583 ms 49440 KB Output is correct
3 Correct 585 ms 49428 KB Output is correct
4 Correct 450 ms 48184 KB Output is correct
5 Correct 31 ms 15268 KB Output is correct
6 Correct 417 ms 38780 KB Output is correct
7 Correct 487 ms 39356 KB Output is correct
8 Correct 509 ms 38408 KB Output is correct
9 Correct 510 ms 38552 KB Output is correct
10 Correct 625 ms 44360 KB Output is correct
11 Correct 626 ms 42988 KB Output is correct
12 Incorrect 33 ms 15240 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 15236 KB Output is correct
2 Correct 47 ms 16256 KB Output is correct
3 Correct 43 ms 16324 KB Output is correct
4 Correct 48 ms 16392 KB Output is correct
5 Correct 53 ms 16576 KB Output is correct
6 Correct 43 ms 15984 KB Output is correct
7 Correct 36 ms 15220 KB Output is correct
8 Correct 177 ms 32392 KB Output is correct
9 Correct 172 ms 32452 KB Output is correct
10 Correct 31 ms 15100 KB Output is correct
11 Correct 572 ms 49364 KB Output is correct
12 Correct 581 ms 49396 KB Output is correct
13 Correct 445 ms 48228 KB Output is correct
14 Correct 32 ms 15268 KB Output is correct
15 Correct 414 ms 38848 KB Output is correct
16 Correct 503 ms 39200 KB Output is correct
17 Correct 510 ms 38460 KB Output is correct
18 Correct 509 ms 38460 KB Output is correct
19 Correct 650 ms 44348 KB Output is correct
20 Correct 620 ms 42996 KB Output is correct
21 Correct 193 ms 35152 KB Output is correct
22 Correct 215 ms 34328 KB Output is correct
23 Correct 378 ms 38384 KB Output is correct
24 Correct 373 ms 38092 KB Output is correct
25 Correct 541 ms 43804 KB Output is correct
26 Correct 470 ms 37164 KB Output is correct
27 Correct 460 ms 37440 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 15236 KB Output is correct
2 Correct 47 ms 16256 KB Output is correct
3 Correct 43 ms 16324 KB Output is correct
4 Correct 48 ms 16392 KB Output is correct
5 Correct 53 ms 16576 KB Output is correct
6 Correct 43 ms 15984 KB Output is correct
7 Correct 36 ms 15220 KB Output is correct
8 Correct 177 ms 32392 KB Output is correct
9 Correct 172 ms 32452 KB Output is correct
10 Correct 31 ms 15100 KB Output is correct
11 Correct 572 ms 49364 KB Output is correct
12 Correct 581 ms 49396 KB Output is correct
13 Correct 445 ms 48228 KB Output is correct
14 Correct 32 ms 15268 KB Output is correct
15 Correct 414 ms 38848 KB Output is correct
16 Correct 503 ms 39200 KB Output is correct
17 Correct 510 ms 38460 KB Output is correct
18 Correct 509 ms 38460 KB Output is correct
19 Correct 650 ms 44348 KB Output is correct
20 Correct 620 ms 42996 KB Output is correct
21 Correct 193 ms 35152 KB Output is correct
22 Correct 215 ms 34328 KB Output is correct
23 Correct 378 ms 38384 KB Output is correct
24 Correct 373 ms 38092 KB Output is correct
25 Correct 541 ms 43804 KB Output is correct
26 Correct 470 ms 37164 KB Output is correct
27 Correct 460 ms 37440 KB Output is correct
28 Incorrect 32 ms 15272 KB Extra information in the output file
29 Halted 0 ms 0 KB -