oj.uz

Submission #540462

# Submission time Handle Problem Language Result Execution time Memory
540462 2022-03-20T12:08:31 Z elazarkoren Inside information (BOI21_servers) C++17
55 / 100
 172 ms 45832 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];
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};
    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 times[MAX_N], l[MAX_N], r[MAX_N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
//    int c = 1;
    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});
            times[min(A, b)] = i;
//            times[max(A, b)] = c;
//            c++;
        } else if (type[i] == 'Q') {
            cin >> a[i] >> d[i];
        } else {
//            int x;
            cin >> d[i];
//            if (x == 1) ans[i] = c;
//            else if (!times[x]) {
//                ans[i] = 1;
//            } else ans[i] = c - times[x] + 1;
//            ans[i] = Dfs(x, -1);
        }
    }
    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);
        }
    }
    times[0] = times[n] = infinity;
    l[1] = 1, r[n] = n;
    for (int i = 2, left = 1; i <= n; i++) {
        if (times[i - 1] > times[i - 2]) left = i - 1;
        l[i] = left;
    }
    for (int i = n - 1, right = n; i; i--) {
        if (times[i] > times[i + 1]) right = i + 1;
        r[i] = right;
    }
    for (int i = 0; i < n + q - 1; i++) {
        if (type[i] == 'Q') {
            ans[i] = Solve(a[i], d[i]) <= i;
        } else if (type[i] == 'C') {
            int begin = l[d[i]], end = d[i], mid;
            while (begin < end) {
                mid = (begin + end) >> 1;
                if (times[mid] > i) {
                    begin = mid + 1;
                } else end = mid;
            }
            int left = begin;
            begin = d[i], end = r[d[i]];
            while (begin < end) {
                mid = (begin + end) >> 1;
                if (times[mid] > i) {
                    end = mid;
                } else begin = mid + 1;
            }
            int right = end;
            ans[i] = right - left + 1;
        }
    }
    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;
}
//4 5
//S 2 3
//C 3
//S 3 4
//C 4
//S 1 2
//C 2
//C 1
//C 4

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 9296 KB Output is correct
2 Correct 38 ms 10024 KB Output is correct
3 Correct 32 ms 10108 KB Output is correct
4 Correct 42 ms 10188 KB Output is correct
5 Correct 38 ms 10316 KB Output is correct
6 Correct 32 ms 10048 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 9296 KB Output is correct
2 Correct 38 ms 10024 KB Output is correct
3 Correct 32 ms 10108 KB Output is correct
4 Correct 42 ms 10188 KB Output is correct
5 Correct 38 ms 10316 KB Output is correct
6 Correct 32 ms 10048 KB Output is correct
7 Incorrect 33 ms 9304 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 26 ms 9340 KB Output is correct
2 Correct 111 ms 34436 KB Output is correct
3 Correct 129 ms 34384 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 9340 KB Output is correct
2 Correct 111 ms 34436 KB Output is correct
3 Correct 129 ms 34384 KB Output is correct
4 Incorrect 24 ms 9320 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 25 ms 9332 KB Output is correct
2 Correct 123 ms 43484 KB Output is correct
3 Correct 119 ms 43344 KB Output is correct
4 Correct 127 ms 43264 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 9332 KB Output is correct
2 Correct 123 ms 43484 KB Output is correct
3 Correct 119 ms 43344 KB Output is correct
4 Correct 127 ms 43264 KB Output is correct
5 Correct 24 ms 9356 KB Output is correct
6 Correct 115 ms 44644 KB Output is correct
7 Correct 132 ms 45800 KB Output is correct
8 Correct 97 ms 45832 KB Output is correct
9 Correct 98 ms 45772 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 9324 KB Output is correct
2 Correct 114 ms 34648 KB Output is correct
3 Correct 128 ms 34448 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 9324 KB Output is correct
2 Correct 114 ms 34648 KB Output is correct
3 Correct 128 ms 34448 KB Output is correct
4 Incorrect 26 ms 9300 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 28 ms 9256 KB Output is correct
2 Correct 125 ms 43356 KB Output is correct
3 Correct 143 ms 43320 KB Output is correct
4 Correct 122 ms 43340 KB Output is correct
5 Correct 24 ms 9356 KB Output is correct
6 Correct 108 ms 34612 KB Output is correct
7 Correct 109 ms 34484 KB Output is correct
8 Correct 149 ms 35612 KB Output is correct
9 Correct 125 ms 35424 KB Output is correct
10 Correct 132 ms 40220 KB Output is correct
11 Correct 170 ms 39500 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 9256 KB Output is correct
2 Correct 125 ms 43356 KB Output is correct
3 Correct 143 ms 43320 KB Output is correct
4 Correct 122 ms 43340 KB Output is correct
5 Correct 24 ms 9356 KB Output is correct
6 Correct 108 ms 34612 KB Output is correct
7 Correct 109 ms 34484 KB Output is correct
8 Correct 149 ms 35612 KB Output is correct
9 Correct 125 ms 35424 KB Output is correct
10 Correct 132 ms 40220 KB Output is correct
11 Correct 170 ms 39500 KB Output is correct
12 Correct 24 ms 9300 KB Output is correct
13 Correct 115 ms 44628 KB Output is correct
14 Correct 116 ms 45524 KB Output is correct
15 Correct 97 ms 45808 KB Output is correct
16 Correct 96 ms 45752 KB Output is correct
17 Incorrect 26 ms 10148 KB Extra information in the output file
18 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 9300 KB Output is correct
2 Correct 38 ms 10068 KB Output is correct
3 Correct 32 ms 10036 KB Output is correct
4 Correct 44 ms 10152 KB Output is correct
5 Correct 39 ms 10240 KB Output is correct
6 Correct 31 ms 10060 KB Output is correct
7 Correct 24 ms 9384 KB Output is correct
8 Correct 117 ms 34396 KB Output is correct
9 Correct 115 ms 34472 KB Output is correct
10 Correct 24 ms 9292 KB Output is correct
11 Correct 114 ms 43468 KB Output is correct
12 Correct 115 ms 43300 KB Output is correct
13 Correct 124 ms 43332 KB Output is correct
14 Correct 24 ms 9300 KB Output is correct
15 Correct 108 ms 34636 KB Output is correct
16 Correct 114 ms 34464 KB Output is correct
17 Correct 145 ms 35716 KB Output is correct
18 Correct 115 ms 35592 KB Output is correct
19 Correct 128 ms 40336 KB Output is correct
20 Correct 172 ms 39520 KB Output is correct
21 Correct 117 ms 34768 KB Output is correct
22 Correct 124 ms 34896 KB Output is correct
23 Correct 116 ms 35132 KB Output is correct
24 Correct 117 ms 35216 KB Output is correct
25 Correct 127 ms 37048 KB Output is correct
26 Correct 109 ms 33580 KB Output is correct
27 Correct 99 ms 33320 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 9300 KB Output is correct
2 Correct 38 ms 10068 KB Output is correct
3 Correct 32 ms 10036 KB Output is correct
4 Correct 44 ms 10152 KB Output is correct
5 Correct 39 ms 10240 KB Output is correct
6 Correct 31 ms 10060 KB Output is correct
7 Correct 24 ms 9384 KB Output is correct
8 Correct 117 ms 34396 KB Output is correct
9 Correct 115 ms 34472 KB Output is correct
10 Correct 24 ms 9292 KB Output is correct
11 Correct 114 ms 43468 KB Output is correct
12 Correct 115 ms 43300 KB Output is correct
13 Correct 124 ms 43332 KB Output is correct
14 Correct 24 ms 9300 KB Output is correct
15 Correct 108 ms 34636 KB Output is correct
16 Correct 114 ms 34464 KB Output is correct
17 Correct 145 ms 35716 KB Output is correct
18 Correct 115 ms 35592 KB Output is correct
19 Correct 128 ms 40336 KB Output is correct
20 Correct 172 ms 39520 KB Output is correct
21 Correct 117 ms 34768 KB Output is correct
22 Correct 124 ms 34896 KB Output is correct
23 Correct 116 ms 35132 KB Output is correct
24 Correct 117 ms 35216 KB Output is correct
25 Correct 127 ms 37048 KB Output is correct
26 Correct 109 ms 33580 KB Output is correct
27 Correct 99 ms 33320 KB Output is correct
28 Incorrect 25 ms 9300 KB Extra information in the output file
29 Halted 0 ms 0 KB -