oj.uz

Submission #540414

# Submission time Handle Problem Language Result Execution time Memory
540414 2022-03-20T10:12:06 Z elazarkoren Inside information (BOI21_servers) C++17
52.5 / 100
 3500 ms 43864 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], ans[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 x;
            cin >> x;
            ans[i] = Dfs(x, -1);
//            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') {
            ans[i] = Solve(a[i], d[i]) <= i;
//            cout << (Solve(a[i], d[i]) <= i ? "yes\n" : "no\n");
        }
    }
    for (int i = 0; i < n + q - 1; i++) {
        if (type[i] == 'Q') {
            cout << (ans[i] ? "yes\n" : "no\n");
        } else if (type[i] == 'C') {
            cout << ans[i] << '\n';
        }
    }
    return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 9564 KB Output is correct
2 Correct 46 ms 10244 KB Output is correct
3 Correct 41 ms 10396 KB Output is correct
4 Correct 63 ms 10472 KB Output is correct
5 Correct 40 ms 10532 KB Output is correct
6 Correct 35 ms 10120 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 9564 KB Output is correct
2 Correct 46 ms 10244 KB Output is correct
3 Correct 41 ms 10396 KB Output is correct
4 Correct 63 ms 10472 KB Output is correct
5 Correct 40 ms 10532 KB Output is correct
6 Correct 35 ms 10120 KB Output is correct
7 Correct 26 ms 9336 KB Output is correct
8 Correct 42 ms 10860 KB Output is correct
9 Correct 252 ms 10288 KB Output is correct
10 Correct 40 ms 10560 KB Output is correct
11 Correct 41 ms 11340 KB Output is correct
12 Correct 894 ms 11200 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 9592 KB Output is correct
2 Correct 173 ms 33864 KB Output is correct
3 Correct 158 ms 33672 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 9592 KB Output is correct
2 Correct 173 ms 33864 KB Output is correct
3 Correct 158 ms 33672 KB Output is correct
4 Correct 31 ms 9528 KB Output is correct
5 Execution timed out 3554 ms 13928 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 9560 KB Output is correct
2 Correct 150 ms 42048 KB Output is correct
3 Correct 147 ms 42324 KB Output is correct
4 Correct 167 ms 43864 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 9560 KB Output is correct
2 Correct 150 ms 42048 KB Output is correct
3 Correct 147 ms 42324 KB Output is correct
4 Correct 167 ms 43864 KB Output is correct
5 Correct 30 ms 9552 KB Output is correct
6 Correct 137 ms 43168 KB Output is correct
7 Execution timed out 3565 ms 15132 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 9448 KB Output is correct
2 Correct 150 ms 33764 KB Output is correct
3 Correct 157 ms 33488 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 9448 KB Output is correct
2 Correct 150 ms 33764 KB Output is correct
3 Correct 157 ms 33488 KB Output is correct
4 Correct 42 ms 9556 KB Output is correct
5 Execution timed out 3529 ms 16700 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 9240 KB Output is correct
2 Correct 156 ms 42016 KB Output is correct
3 Correct 159 ms 42304 KB Output is correct
4 Correct 160 ms 43736 KB Output is correct
5 Correct 27 ms 10072 KB Output is correct
6 Correct 131 ms 34452 KB Output is correct
7 Correct 171 ms 33796 KB Output is correct
8 Correct 202 ms 35624 KB Output is correct
9 Correct 157 ms 35524 KB Output is correct
10 Correct 155 ms 39756 KB Output is correct
11 Correct 241 ms 38820 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 27 ms 9240 KB Output is correct
2 Correct 156 ms 42016 KB Output is correct
3 Correct 159 ms 42304 KB Output is correct
4 Correct 160 ms 43736 KB Output is correct
5 Correct 27 ms 10072 KB Output is correct
6 Correct 131 ms 34452 KB Output is correct
7 Correct 171 ms 33796 KB Output is correct
8 Correct 202 ms 35624 KB Output is correct
9 Correct 157 ms 35524 KB Output is correct
10 Correct 155 ms 39756 KB Output is correct
11 Correct 241 ms 38820 KB Output is correct
12 Correct 27 ms 9292 KB Output is correct
13 Correct 144 ms 43288 KB Output is correct
14 Execution timed out 3587 ms 15480 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 9612 KB Output is correct
2 Correct 41 ms 10252 KB Output is correct
3 Correct 35 ms 10120 KB Output is correct
4 Correct 45 ms 10376 KB Output is correct
5 Correct 42 ms 10528 KB Output is correct
6 Correct 39 ms 9996 KB Output is correct
7 Correct 26 ms 9352 KB Output is correct
8 Correct 176 ms 33740 KB Output is correct
9 Correct 152 ms 35008 KB Output is correct
10 Correct 27 ms 9576 KB Output is correct
11 Correct 172 ms 42264 KB Output is correct
12 Correct 146 ms 42276 KB Output is correct
13 Correct 159 ms 42496 KB Output is correct
14 Correct 27 ms 9300 KB Output is correct
15 Correct 130 ms 34620 KB Output is correct
16 Correct 154 ms 34280 KB Output is correct
17 Correct 210 ms 35656 KB Output is correct
18 Correct 170 ms 34364 KB Output is correct
19 Correct 173 ms 39756 KB Output is correct
20 Correct 228 ms 38412 KB Output is correct
21 Correct 172 ms 34408 KB Output is correct
22 Correct 198 ms 33488 KB Output is correct
23 Correct 150 ms 35300 KB Output is correct
24 Correct 162 ms 34360 KB Output is correct
25 Correct 154 ms 36956 KB Output is correct
26 Correct 137 ms 33100 KB Output is correct
27 Correct 144 ms 32024 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 29 ms 9612 KB Output is correct
2 Correct 41 ms 10252 KB Output is correct
3 Correct 35 ms 10120 KB Output is correct
4 Correct 45 ms 10376 KB Output is correct
5 Correct 42 ms 10528 KB Output is correct
6 Correct 39 ms 9996 KB Output is correct
7 Correct 26 ms 9352 KB Output is correct
8 Correct 176 ms 33740 KB Output is correct
9 Correct 152 ms 35008 KB Output is correct
10 Correct 27 ms 9576 KB Output is correct
11 Correct 172 ms 42264 KB Output is correct
12 Correct 146 ms 42276 KB Output is correct
13 Correct 159 ms 42496 KB Output is correct
14 Correct 27 ms 9300 KB Output is correct
15 Correct 130 ms 34620 KB Output is correct
16 Correct 154 ms 34280 KB Output is correct
17 Correct 210 ms 35656 KB Output is correct
18 Correct 170 ms 34364 KB Output is correct
19 Correct 173 ms 39756 KB Output is correct
20 Correct 228 ms 38412 KB Output is correct
21 Correct 172 ms 34408 KB Output is correct
22 Correct 198 ms 33488 KB Output is correct
23 Correct 150 ms 35300 KB Output is correct
24 Correct 162 ms 34360 KB Output is correct
25 Correct 154 ms 36956 KB Output is correct
26 Correct 137 ms 33100 KB Output is correct
27 Correct 144 ms 32024 KB Output is correct
28 Correct 31 ms 9432 KB Output is correct
29 Correct 44 ms 10976 KB Output is correct
30 Correct 242 ms 9976 KB Output is correct
31 Correct 43 ms 11096 KB Output is correct
32 Correct 39 ms 10176 KB Output is correct
33 Correct 892 ms 10700 KB Output is correct
34 Correct 30 ms 9992 KB Output is correct
35 Execution timed out 3565 ms 13600 KB Time limit exceeded
36 Halted 0 ms 0 KB -