oj.uz

답안 #540461

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
540461 2022-03-20T11:54:55 Z elazarkoren Inside information (BOI21_servers) C++17
52.5 / 100
 211 ms 42496 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];

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[max(A, b)] = c;
            c++;
        } else if (type[i] == 'Q') {
            cin >> a[i] >> d[i];
        } else {
            int x;
            cin >> x;
            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);
        }
    }
    for (int i = 0; i < n + q - 1; i++) {
        if (type[i] == 'Q') {
            ans[i] = Solve(a[i], d[i]) <= i;
        }
    }
    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
//C 1
//S 1 3
//C 2
//S 1 2
//C 3
//S 1 4
//C 4
//C 2

Subtask #1
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 9292 KB Output is correct
2 Correct 40 ms 9924 KB Output is correct
3 Correct 34 ms 10024 KB Output is correct
4 Correct 41 ms 10056 KB Output is correct
5 Correct 37 ms 10292 KB Output is correct
6 Correct 30 ms 10008 KB Output is correct

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 9292 KB Output is correct
2 Correct 40 ms 9924 KB Output is correct
3 Correct 34 ms 10024 KB Output is correct
4 Correct 41 ms 10056 KB Output is correct
5 Correct 37 ms 10292 KB Output is correct
6 Correct 30 ms 10008 KB Output is correct
7 Incorrect 28 ms 9300 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 9344 KB Output is correct
2 Correct 133 ms 33920 KB Output is correct
3 Correct 117 ms 33952 KB Output is correct

Subtask #4
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 9344 KB Output is correct
2 Correct 133 ms 33920 KB Output is correct
3 Correct 117 ms 33952 KB Output is correct
4 Correct 25 ms 9304 KB Output is correct
5 Correct 115 ms 36156 KB Output is correct
6 Correct 77 ms 34024 KB Output is correct
7 Correct 74 ms 36012 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 9300 KB Output is correct
2 Correct 130 ms 42444 KB Output is correct
3 Correct 127 ms 42492 KB Output is correct
4 Correct 130 ms 42360 KB Output is correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 9300 KB Output is correct
2 Correct 130 ms 42444 KB Output is correct
3 Correct 127 ms 42492 KB Output is correct
4 Correct 130 ms 42360 KB Output is correct
5 Incorrect 28 ms 9300 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 9344 KB Output is correct
2 Correct 109 ms 33944 KB Output is correct
3 Correct 145 ms 33720 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 9344 KB Output is correct
2 Correct 109 ms 33944 KB Output is correct
3 Correct 145 ms 33720 KB Output is correct
4 Incorrect 27 ms 9252 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 9276 KB Output is correct
2 Correct 129 ms 42388 KB Output is correct
3 Correct 136 ms 42408 KB Output is correct
4 Correct 128 ms 42340 KB Output is correct
5 Correct 28 ms 9300 KB Output is correct
6 Correct 112 ms 33896 KB Output is correct
7 Correct 117 ms 33676 KB Output is correct
8 Correct 167 ms 34600 KB Output is correct
9 Correct 127 ms 34860 KB Output is correct
10 Correct 127 ms 39244 KB Output is correct
11 Correct 195 ms 38608 KB Output is correct

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 9276 KB Output is correct
2 Correct 129 ms 42388 KB Output is correct
3 Correct 136 ms 42408 KB Output is correct
4 Correct 128 ms 42340 KB Output is correct
5 Correct 28 ms 9300 KB Output is correct
6 Correct 112 ms 33896 KB Output is correct
7 Correct 117 ms 33676 KB Output is correct
8 Correct 167 ms 34600 KB Output is correct
9 Correct 127 ms 34860 KB Output is correct
10 Correct 127 ms 39244 KB Output is correct
11 Correct 195 ms 38608 KB Output is correct
12 Incorrect 24 ms 9264 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 9344 KB Output is correct
2 Correct 37 ms 10012 KB Output is correct
3 Correct 32 ms 10104 KB Output is correct
4 Correct 42 ms 10060 KB Output is correct
5 Correct 42 ms 10316 KB Output is correct
6 Correct 31 ms 10072 KB Output is correct
7 Correct 23 ms 9300 KB Output is correct
8 Correct 113 ms 34008 KB Output is correct
9 Correct 132 ms 33944 KB Output is correct
10 Correct 24 ms 9300 KB Output is correct
11 Correct 114 ms 42496 KB Output is correct
12 Correct 133 ms 42344 KB Output is correct
13 Correct 127 ms 42464 KB Output is correct
14 Correct 27 ms 9300 KB Output is correct
15 Correct 104 ms 33948 KB Output is correct
16 Correct 134 ms 33748 KB Output is correct
17 Correct 149 ms 34616 KB Output is correct
18 Correct 139 ms 34920 KB Output is correct
19 Correct 161 ms 39244 KB Output is correct
20 Correct 211 ms 38604 KB Output is correct
21 Correct 120 ms 33848 KB Output is correct
22 Correct 152 ms 33648 KB Output is correct
23 Correct 123 ms 34428 KB Output is correct
24 Correct 123 ms 34400 KB Output is correct
25 Correct 139 ms 36192 KB Output is correct
26 Correct 136 ms 32448 KB Output is correct
27 Correct 104 ms 32376 KB Output is correct

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 9344 KB Output is correct
2 Correct 37 ms 10012 KB Output is correct
3 Correct 32 ms 10104 KB Output is correct
4 Correct 42 ms 10060 KB Output is correct
5 Correct 42 ms 10316 KB Output is correct
6 Correct 31 ms 10072 KB Output is correct
7 Correct 23 ms 9300 KB Output is correct
8 Correct 113 ms 34008 KB Output is correct
9 Correct 132 ms 33944 KB Output is correct
10 Correct 24 ms 9300 KB Output is correct
11 Correct 114 ms 42496 KB Output is correct
12 Correct 133 ms 42344 KB Output is correct
13 Correct 127 ms 42464 KB Output is correct
14 Correct 27 ms 9300 KB Output is correct
15 Correct 104 ms 33948 KB Output is correct
16 Correct 134 ms 33748 KB Output is correct
17 Correct 149 ms 34616 KB Output is correct
18 Correct 139 ms 34920 KB Output is correct
19 Correct 161 ms 39244 KB Output is correct
20 Correct 211 ms 38604 KB Output is correct
21 Correct 120 ms 33848 KB Output is correct
22 Correct 152 ms 33648 KB Output is correct
23 Correct 123 ms 34428 KB Output is correct
24 Correct 123 ms 34400 KB Output is correct
25 Correct 139 ms 36192 KB Output is correct
26 Correct 136 ms 32448 KB Output is correct
27 Correct 104 ms 32376 KB Output is correct
28 Incorrect 25 ms 9300 KB Extra information in the output file
29 Halted 0 ms 0 KB -