oj.uz

Submission #638098

# Submission time Handle Problem Language Result Execution time Memory
638098 2022-09-04T15:15:18 Z LeonaRaging Inside information (BOI21_servers) C++14
100 / 100
 1129 ms 61564 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define ll long long
#define pb push_back
#define db(val) "[" #val " = " << (val) << "] "

const ll mod = 1e9 + 7;
const int maxn = 2e5 + 5e4 + 4;
const int INF = 1e9;

struct Node {
    int fi, se;
    bool operator < (const Node &other) const {
        return se > other.se;
    }
};

struct seg_tree {
    vector<int> t;
    seg_tree() {
        t.resize(4 * maxn);
    }
    void update(int pos, int val, int v = 1, int l = 1, int r = maxn - 1) {
        if (l == r) {
            t[v] += val;
            return;
        }
        int m = (l + r) / 2;
        if (pos <= m) update(pos, val, 2 * v, l, m);
        else update(pos, val, 2 * v + 1, m + 1, r);
        t[v] = t[2 * v] + t[2 * v + 1];
    }
    int get(int r, int l = 1, int v = 1, int tl = 1, int tr = maxn - 1) {
        if (tl > r || tr < l) return 0;
        if (tl >= l && tr <= r) return t[v];
        int m = (tl + tr) / 2;
        int L = get(r, l, 2 * v, tl, m);
        int R = get(r, l, 2 * v + 1, m + 1, tr);
        return L + R;
    }
} IT;

int n, k, res[maxn];
set<Node> adj[maxn];
vector<int> query_c[maxn], cur;
set<pair<int,int>> query_q[maxn];
map<int,int> L;
stack<pair<int,int>> rev;

void dfs_in(int u, int p, int pre) {
    auto it = query_q[u].begin();
    while (it != query_q[u].end()) {
        auto idx = L.find(it->fi);
        if (idx == L.end() || idx->se > it->se) {
            it++;
            continue;
        }
        res[it->se] = -1;
        it = query_q[u].erase(it);
    }
    cur.push_back(u);
    for (auto it : adj[u]) {
        int v = it.fi, w = it.se;
        if (w < pre && v != p)
            dfs_in(v, u, w);
    }
}

void dfs_out(int u, int p, int pre) {
    L[u] = pre;
    IT.update(pre, 1);
    rev.push({pre, 1});
    for (auto it : adj[u]) {
        int v = it.fi, w = it.se;
        if (w > pre && v != p)
            dfs_out(v, u, w);
    }
}

void Solve(int u) {
    L.clear();
    for (auto it : adj[u]) {
        cur.clear();
        int v = it.fi, w = it.se;
        L[u] = w;
        dfs_in(v, u, w);
        for (auto i : cur) {
            for (auto it : query_c[i]) if (it > w)
                res[it] += IT.get(it) + 1;
        }
        dfs_out(v, u, w);
    }
    auto it = query_q[u].begin();
    while (it != query_q[u].end()) {
        auto idx = L.find(it->fi);
        if (idx == L.end() || idx->se > it->se) {
            it++;
            continue;
        }
        res[it->se] = -1;
        it = query_q[u].erase(it);
    }
    for (auto it : query_c[u]) {
        res[it] += IT.get(it) + 1;
    }
    while (!rev.empty()) {
        int u, i; tie(u, i) = rev.top(); rev.pop();
        IT.update(u, -i);
    }    
}

struct Centroid_Decomposition {
    int sz[maxn];
    int dfs(int u, int p) {
        sz[u] = 1;
        for (auto it : adj[u])
            if (it.fi != p)
                sz[u] += dfs(it.fi, u);
        return sz[u];
    }
    int Centroid(int u, int p, int tot) {
        for (auto it : adj[u])
            if (it.fi != p && sz[it.fi] > tot / 2)
                return Centroid(it.fi, u, tot);
        return u;
    }
    void build(int u) {
        int tot = dfs(u, 0);
        int c = Centroid(u, 0, tot);
        Solve(c);
        vector<Node> del(adj[c].begin(), adj[c].end());
        for (auto it : del) {
            adj[c].erase(it);
            adj[it.fi].erase(adj[it.fi].find({c, it.se}));
            build(it.fi);
        }
    }
} Cen;

int main()
{
    // ios::sync_with_stdio(0);
    // cin.tie(0); cout.tie(0);
    //freopen(".INP", "r", stdin);
    //freopen(".OUT", "w", stdout);
    cin >> n >> k;
    for (int i = 1; i <= n + k - 1; i++)
        res[i] = -3;
    for (int i = 1; i <= n + k - 1; i++) {
        char type; int u; cin >> type >> u;
        if (type == 'S') {
            int v; cin >> v;
            adj[u].insert({v, i});
            adj[v].insert({u, i});
        }
        else if (type == 'Q') {
            int v; cin >> v;
            if (u == v) res[i] = -1;
            else {
                query_q[v].insert({u, i});
                res[i] = -2;
            }
        }
        else {
            query_c[u].pb(i);
            res[i] = 0;
        }
    }
    Cen.build(1);
    for (int i = 1; i <= n + k - 1; i++)
        if (res[i] != -3) {
            if (res[i] >= 0) cout << res[i];
            else cout << (res[i] == -1 ? "yes" : "no");
            cout << '\n';
        }
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 97 ms 40092 KB Output is correct
2 Correct 125 ms 40440 KB Output is correct
3 Correct 131 ms 40336 KB Output is correct
4 Correct 177 ms 40468 KB Output is correct
5 Correct 136 ms 40396 KB Output is correct
6 Correct 131 ms 40572 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 97 ms 40092 KB Output is correct
2 Correct 125 ms 40440 KB Output is correct
3 Correct 131 ms 40336 KB Output is correct
4 Correct 177 ms 40468 KB Output is correct
5 Correct 136 ms 40396 KB Output is correct
6 Correct 131 ms 40572 KB Output is correct
7 Correct 98 ms 39668 KB Output is correct
8 Correct 148 ms 39064 KB Output is correct
9 Correct 118 ms 39116 KB Output is correct
10 Correct 128 ms 39144 KB Output is correct
11 Correct 148 ms 39232 KB Output is correct
12 Correct 117 ms 39208 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 95 ms 39988 KB Output is correct
2 Correct 453 ms 57364 KB Output is correct
3 Correct 460 ms 57420 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 95 ms 39988 KB Output is correct
2 Correct 453 ms 57364 KB Output is correct
3 Correct 460 ms 57420 KB Output is correct
4 Correct 99 ms 39756 KB Output is correct
5 Correct 412 ms 59412 KB Output is correct
6 Correct 305 ms 55956 KB Output is correct
7 Correct 304 ms 56280 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 39944 KB Output is correct
2 Correct 497 ms 54496 KB Output is correct
3 Correct 513 ms 54648 KB Output is correct
4 Correct 566 ms 61348 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 39944 KB Output is correct
2 Correct 497 ms 54496 KB Output is correct
3 Correct 513 ms 54648 KB Output is correct
4 Correct 566 ms 61348 KB Output is correct
5 Correct 95 ms 39756 KB Output is correct
6 Correct 503 ms 56872 KB Output is correct
7 Correct 610 ms 61564 KB Output is correct
8 Correct 536 ms 55508 KB Output is correct
9 Correct 518 ms 55488 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 39928 KB Output is correct
2 Correct 567 ms 55280 KB Output is correct
3 Correct 439 ms 50508 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 39928 KB Output is correct
2 Correct 567 ms 55280 KB Output is correct
3 Correct 439 ms 50508 KB Output is correct
4 Correct 92 ms 39768 KB Output is correct
5 Correct 655 ms 56872 KB Output is correct
6 Correct 477 ms 52864 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 91 ms 40020 KB Output is correct
2 Correct 534 ms 54492 KB Output is correct
3 Correct 484 ms 54476 KB Output is correct
4 Correct 578 ms 61296 KB Output is correct
5 Correct 95 ms 39928 KB Output is correct
6 Correct 600 ms 55164 KB Output is correct
7 Correct 465 ms 50568 KB Output is correct
8 Correct 443 ms 52044 KB Output is correct
9 Correct 484 ms 51096 KB Output is correct
10 Correct 730 ms 53280 KB Output is correct
11 Correct 733 ms 54812 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 91 ms 40020 KB Output is correct
2 Correct 534 ms 54492 KB Output is correct
3 Correct 484 ms 54476 KB Output is correct
4 Correct 578 ms 61296 KB Output is correct
5 Correct 95 ms 39928 KB Output is correct
6 Correct 600 ms 55164 KB Output is correct
7 Correct 465 ms 50568 KB Output is correct
8 Correct 443 ms 52044 KB Output is correct
9 Correct 484 ms 51096 KB Output is correct
10 Correct 730 ms 53280 KB Output is correct
11 Correct 733 ms 54812 KB Output is correct
12 Correct 90 ms 39756 KB Output is correct
13 Correct 519 ms 56856 KB Output is correct
14 Correct 587 ms 61384 KB Output is correct
15 Correct 535 ms 55572 KB Output is correct
16 Correct 507 ms 55492 KB Output is correct
17 Correct 116 ms 40580 KB Output is correct
18 Correct 633 ms 56952 KB Output is correct
19 Correct 491 ms 52856 KB Output is correct
20 Correct 516 ms 53688 KB Output is correct
21 Correct 499 ms 53240 KB Output is correct
22 Correct 671 ms 54936 KB Output is correct
23 Correct 962 ms 56268 KB Output is correct
24 Correct 803 ms 57660 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 92 ms 39944 KB Output is correct
2 Correct 128 ms 40388 KB Output is correct
3 Correct 142 ms 40308 KB Output is correct
4 Correct 136 ms 40484 KB Output is correct
5 Correct 139 ms 40672 KB Output is correct
6 Correct 132 ms 40524 KB Output is correct
7 Correct 100 ms 40016 KB Output is correct
8 Correct 475 ms 57456 KB Output is correct
9 Correct 434 ms 57376 KB Output is correct
10 Correct 87 ms 40016 KB Output is correct
11 Correct 482 ms 54560 KB Output is correct
12 Correct 505 ms 54532 KB Output is correct
13 Correct 631 ms 61444 KB Output is correct
14 Correct 95 ms 39972 KB Output is correct
15 Correct 573 ms 55164 KB Output is correct
16 Correct 474 ms 50524 KB Output is correct
17 Correct 445 ms 52040 KB Output is correct
18 Correct 497 ms 51096 KB Output is correct
19 Correct 688 ms 53268 KB Output is correct
20 Correct 711 ms 54768 KB Output is correct
21 Correct 561 ms 57028 KB Output is correct
22 Correct 598 ms 55464 KB Output is correct
23 Correct 552 ms 52244 KB Output is correct
24 Correct 586 ms 52304 KB Output is correct
25 Correct 600 ms 54896 KB Output is correct
26 Correct 445 ms 50504 KB Output is correct
27 Correct 443 ms 50424 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 92 ms 39944 KB Output is correct
2 Correct 128 ms 40388 KB Output is correct
3 Correct 142 ms 40308 KB Output is correct
4 Correct 136 ms 40484 KB Output is correct
5 Correct 139 ms 40672 KB Output is correct
6 Correct 132 ms 40524 KB Output is correct
7 Correct 100 ms 40016 KB Output is correct
8 Correct 475 ms 57456 KB Output is correct
9 Correct 434 ms 57376 KB Output is correct
10 Correct 87 ms 40016 KB Output is correct
11 Correct 482 ms 54560 KB Output is correct
12 Correct 505 ms 54532 KB Output is correct
13 Correct 631 ms 61444 KB Output is correct
14 Correct 95 ms 39972 KB Output is correct
15 Correct 573 ms 55164 KB Output is correct
16 Correct 474 ms 50524 KB Output is correct
17 Correct 445 ms 52040 KB Output is correct
18 Correct 497 ms 51096 KB Output is correct
19 Correct 688 ms 53268 KB Output is correct
20 Correct 711 ms 54768 KB Output is correct
21 Correct 561 ms 57028 KB Output is correct
22 Correct 598 ms 55464 KB Output is correct
23 Correct 552 ms 52244 KB Output is correct
24 Correct 586 ms 52304 KB Output is correct
25 Correct 600 ms 54896 KB Output is correct
26 Correct 445 ms 50504 KB Output is correct
27 Correct 443 ms 50424 KB Output is correct
28 Correct 122 ms 39716 KB Output is correct
29 Correct 121 ms 39120 KB Output is correct
30 Correct 120 ms 39048 KB Output is correct
31 Correct 134 ms 39140 KB Output is correct
32 Correct 129 ms 39184 KB Output is correct
33 Correct 116 ms 39176 KB Output is correct
34 Correct 98 ms 40604 KB Output is correct
35 Correct 484 ms 59360 KB Output is correct
36 Correct 327 ms 55948 KB Output is correct
37 Correct 353 ms 56228 KB Output is correct
38 Correct 111 ms 40548 KB Output is correct
39 Correct 546 ms 56860 KB Output is correct
40 Correct 697 ms 61352 KB Output is correct
41 Correct 573 ms 55508 KB Output is correct
42 Correct 585 ms 55580 KB Output is correct
43 Correct 107 ms 40536 KB Output is correct
44 Correct 694 ms 56956 KB Output is correct
45 Correct 547 ms 52852 KB Output is correct
46 Correct 509 ms 53636 KB Output is correct
47 Correct 581 ms 53172 KB Output is correct
48 Correct 815 ms 54944 KB Output is correct
49 Correct 1129 ms 56300 KB Output is correct
50 Correct 1077 ms 57732 KB Output is correct
51 Correct 485 ms 57008 KB Output is correct
52 Correct 357 ms 56972 KB Output is correct
53 Correct 349 ms 56644 KB Output is correct
54 Correct 373 ms 57100 KB Output is correct
55 Correct 447 ms 53892 KB Output is correct
56 Correct 563 ms 52724 KB Output is correct
57 Correct 545 ms 55504 KB Output is correct
58 Correct 710 ms 52392 KB Output is correct
59 Correct 544 ms 53604 KB Output is correct