oj.uz

Submission #540410

# Submission time Handle Problem Language Result Execution time Memory
540410 2022-03-20T10:07:57 Z elazarkoren Inside information (BOI21_servers) C++17
50 / 100
 181 ms 44368 KB 
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;

const int MAX_N = 3e5;
const int infinity = 1e9;

vii tree[MAX_N];

int depth[MAX_N];
pii dp[20][MAX_N];// weight[MAX_N];
int increase[MAX_N], decrease[MAX_N];
int loga[MAX_N];

void Dfs(int node, int parent, int w, int len_i, int len_d, int dist) {
    depth[node] = dist;
    dp[0][node] = {parent, w};
//    weight[node] = w;
    increase[node] = len_i, decrease[node] = len_d;
    for (auto [neighbor, d] : tree[node]) {
        if (neighbor == parent) continue;
        Dfs(neighbor, node, d, (w > d ? len_i : 0) + 1, (w < d ? len_d : 0) + 1, dist + 1);
    }
}

bool Dfs(int node, int end, int w) {
    if (node == end) return true;
    for (auto [neighbor, d] : tree[node]) {
        if (d >= w) continue;
        if (Dfs(neighbor, end, d)) {
            return true;
        }
    }
    return false;
}

int Dfs(int node, int w) {
    int c = 1;
    for (auto [neighbor, d] : tree[node]) {
        if (d <= w) continue;
        c += Dfs(neighbor, d);
    }
    return c;
}

int n, q;

pii Jump(int a, int k) {
    int max_w = 0;
    for (int i = 0; i <= loga[n]; i++) {
        if ((k >> i) & 1) {
            chkmax(max_w, dp[i][a].y);
            a = dp[i][a].x;
        }
    }
    return {a, max_w};
}

int Solve(int v, int u) {
    if (u == v) return 0;
    int a = v, b = u;
    int max_w = 0;
    if (depth[a] > depth[b]) {
        pii p = Jump(a, depth[a] - depth[b]);
        a = p.x, max_w = p.y;
    } else {
        pii p = Jump(b, depth[b] - depth[a]);
        b = p.x, max_w = p.y;
    }
    bool bad = a != b;
    for (int i = loga[n]; i >= 0; i--) {
        if (dp[i][a].x != dp[i][b].x) {
            chkmax(max_w, dp[i][a].y);
            chkmax(max_w, dp[i][b].y);
            a = dp[i][a].x, b = dp[i][b].x;
        }
    }
    int dep_lca = depth[a] - bad;
    if (bad) {
        chkmax(max_w, dp[0][a].y);
        chkmax(max_w, dp[0][b].y);
    }
    if (dep_lca < depth[v] - decrease[v] || dep_lca < depth[u] - increase[u]) {
        return infinity;
    }
    return (!bad || dp[0][a].y > dp[0][b].y ? max_w : infinity);
}

char type[MAX_N];
int a[MAX_N], d[MAX_N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 0; i < n + q - 1; i++) {
        cin >> type[i];
        if (type[i] == 'S') {
            int A, b;
            cin >> A >> b;
            tree[A].push_back({b, i});
            tree[b].push_back({A, i});
        } else if (type[i] == 'Q') {
//            int a, d;
            cin >> a[i] >> d[i];
//            cout << (Dfs(a, d, infinity) ? "yes\n" : "no\n");
        } else {
//            int d;
            cin >> d[i];
//            cout << Dfs(d, -1) << '\n';
        }
    }
    for (int i = 2; i <= n; i++) {
        loga[i] = loga[i >> 1] + 1;
    }
    Dfs(1, 0, 0, 0, 0, 0);
    for (int i = 1; i <= loga[n]; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j].x = dp[i - 1][dp[i - 1][j].x].x;
            dp[i][j].y = max(dp[i - 1][j].y, dp[i - 1][dp[i - 1][j].x].y);
        }
    }
    for (int i = 0; i < n + q - 1; i++) {
        if (type[i] == 'Q') {
            cout << (Solve(a[i], d[i]) <= i ? "yes\n" : "no\n");
        } else if (type[i] == 'C') {
            cout << Dfs(d[i], -1) << '\n';
        }
    }
    return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 8788 KB Output is correct
2 Correct 36 ms 9532 KB Output is correct
3 Correct 33 ms 9556 KB Output is correct
4 Correct 43 ms 9568 KB Output is correct
5 Correct 37 ms 9776 KB Output is correct
6 Correct 31 ms 9576 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 8788 KB Output is correct
2 Correct 36 ms 9532 KB Output is correct
3 Correct 33 ms 9556 KB Output is correct
4 Correct 43 ms 9568 KB Output is correct
5 Correct 37 ms 9776 KB Output is correct
6 Correct 31 ms 9576 KB Output is correct
7 Incorrect 27 ms 8860 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 22 ms 8860 KB Output is correct
2 Correct 115 ms 32920 KB Output is correct
3 Correct 114 ms 35356 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 8860 KB Output is correct
2 Correct 115 ms 32920 KB Output is correct
3 Correct 114 ms 35356 KB Output is correct
4 Incorrect 26 ms 9716 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 27 ms 8876 KB Output is correct
2 Correct 112 ms 40932 KB Output is correct
3 Correct 113 ms 41164 KB Output is correct
4 Correct 139 ms 43016 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 8876 KB Output is correct
2 Correct 112 ms 40932 KB Output is correct
3 Correct 113 ms 41164 KB Output is correct
4 Correct 139 ms 43016 KB Output is correct
5 Incorrect 26 ms 9632 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 25 ms 8780 KB Output is correct
2 Correct 110 ms 32852 KB Output is correct
3 Correct 115 ms 35816 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 8780 KB Output is correct
2 Correct 110 ms 32852 KB Output is correct
3 Correct 115 ms 35816 KB Output is correct
4 Incorrect 27 ms 9660 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 27 ms 8916 KB Output is correct
2 Correct 124 ms 40976 KB Output is correct
3 Correct 115 ms 41164 KB Output is correct
4 Correct 126 ms 42824 KB Output is correct
5 Correct 25 ms 9676 KB Output is correct
6 Correct 114 ms 35920 KB Output is correct
7 Correct 117 ms 35820 KB Output is correct
8 Correct 149 ms 36712 KB Output is correct
9 Correct 140 ms 36608 KB Output is correct
10 Correct 126 ms 41236 KB Output is correct
11 Correct 178 ms 40524 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 8916 KB Output is correct
2 Correct 124 ms 40976 KB Output is correct
3 Correct 115 ms 41164 KB Output is correct
4 Correct 126 ms 42824 KB Output is correct
5 Correct 25 ms 9676 KB Output is correct
6 Correct 114 ms 35920 KB Output is correct
7 Correct 117 ms 35820 KB Output is correct
8 Correct 149 ms 36712 KB Output is correct
9 Correct 140 ms 36608 KB Output is correct
10 Correct 126 ms 41236 KB Output is correct
11 Correct 178 ms 40524 KB Output is correct
12 Incorrect 30 ms 9676 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 26 ms 8788 KB Output is correct
2 Correct 38 ms 9420 KB Output is correct
3 Correct 32 ms 9572 KB Output is correct
4 Correct 42 ms 9608 KB Output is correct
5 Correct 37 ms 9708 KB Output is correct
6 Correct 31 ms 9520 KB Output is correct
7 Correct 23 ms 8904 KB Output is correct
8 Correct 112 ms 32896 KB Output is correct
9 Correct 130 ms 35372 KB Output is correct
10 Correct 27 ms 9684 KB Output is correct
11 Correct 114 ms 44364 KB Output is correct
12 Correct 117 ms 44368 KB Output is correct
13 Correct 136 ms 44340 KB Output is correct
14 Correct 27 ms 9672 KB Output is correct
15 Correct 111 ms 35804 KB Output is correct
16 Correct 112 ms 35844 KB Output is correct
17 Correct 159 ms 36876 KB Output is correct
18 Correct 124 ms 36648 KB Output is correct
19 Correct 125 ms 41164 KB Output is correct
20 Correct 181 ms 40568 KB Output is correct
21 Correct 114 ms 35876 KB Output is correct
22 Correct 122 ms 35984 KB Output is correct
23 Correct 119 ms 36172 KB Output is correct
24 Correct 124 ms 36356 KB Output is correct
25 Correct 127 ms 38080 KB Output is correct
26 Correct 114 ms 34980 KB Output is correct
27 Correct 104 ms 34816 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 8788 KB Output is correct
2 Correct 38 ms 9420 KB Output is correct
3 Correct 32 ms 9572 KB Output is correct
4 Correct 42 ms 9608 KB Output is correct
5 Correct 37 ms 9708 KB Output is correct
6 Correct 31 ms 9520 KB Output is correct
7 Correct 23 ms 8904 KB Output is correct
8 Correct 112 ms 32896 KB Output is correct
9 Correct 130 ms 35372 KB Output is correct
10 Correct 27 ms 9684 KB Output is correct
11 Correct 114 ms 44364 KB Output is correct
12 Correct 117 ms 44368 KB Output is correct
13 Correct 136 ms 44340 KB Output is correct
14 Correct 27 ms 9672 KB Output is correct
15 Correct 111 ms 35804 KB Output is correct
16 Correct 112 ms 35844 KB Output is correct
17 Correct 159 ms 36876 KB Output is correct
18 Correct 124 ms 36648 KB Output is correct
19 Correct 125 ms 41164 KB Output is correct
20 Correct 181 ms 40568 KB Output is correct
21 Correct 114 ms 35876 KB Output is correct
22 Correct 122 ms 35984 KB Output is correct
23 Correct 119 ms 36172 KB Output is correct
24 Correct 124 ms 36356 KB Output is correct
25 Correct 127 ms 38080 KB Output is correct
26 Correct 114 ms 34980 KB Output is correct
27 Correct 104 ms 34816 KB Output is correct
28 Incorrect 29 ms 9668 KB Extra information in the output file
29 Halted 0 ms 0 KB -