oj.uz

Submission #560284

# Submission time Handle Problem Language Result Execution time Memory
560284 2022-05-11T08:41:35 Z Ooops_sorry Inside information (BOI21_servers) C++14
57.5 / 100
 3500 ms 39700 KB 
#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define ld long double
#define ll long long

mt19937 rnd(51);

const int N = 2.5e5 + 10, INF = 1e9;
vector<pair<int,int>> g[N], need1[N];
vector<int> sz(N), ans(N), val(N), fir(N), need2[N];
vector<bool> used(N), good(N);
vector<int> arr;

void zhfs(int v, int p) {
    sz[v] = 1;
    for (auto to : g[v]) {
        if (to.first != p && !used[to.first]) {
            zhfs(to.first, v);
            sz[v] += sz[to.first];
        }
    }
}

int find_centroid(int v, int p, int n) {
    for (auto to : g[v]) {
        if (to.first != p && !used[to.first] && sz[to.first] > n / 2) {
            return find_centroid(to.first, v, n);
        }
    }
    return v;
}

void dfs1(int v, int p, int last, int first_val) {
    val[v] = last;
    fir[v] = first_val;
    good[v] = 1;
    arr.pb(v);
    for (auto to : g[v]) {
        if (to.first != p && !used[to.first] && to.second > last) {
            dfs1(to.first, v, to.second, (last == -INF ? to.second : first_val));
        }
    }
}

void dfs2(int v, int p, int last, int first_val) {
    for (auto to : need1[v]) {
        if (first_val == fir[to.first]) continue;
        if (good[to.first] && max({first_val, val[to.first]}) < to.second && first_val < fir[to.first]) {
            ans[to.second] = INF;
        }
    }
    for (auto to : need2[v]) {
        if (first_val > to) continue;
        for (auto u : arr) {
            if (fir[u] > first_val && val[u] < to) {
                ans[to]++;
            }
        }
    }
    for (auto to : g[v]) {
        if (to.first != p && !used[to.first] && to.second < last) {
            dfs2(to.first, v, to.second, (last == INF ? to.second : first_val));
        }
    }
}

void solve(int v) {
    zhfs(v, -1);
    arr.clear();
    dfs1(v, -1, -INF, INF);
    dfs2(v, -1, INF, -INF);
    for (auto to : arr) {
        good[to] = 0;
    }
    used[v] = 1;
    for (auto to : g[v]) {
        if (!used[to.first]) {
            solve(find_centroid(to.first, v, sz[to.first]));
        }
    }
}

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif // LCOAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n + k - 1; i++) {
        char c;
        cin >> c;
        if (c == 'S') {
            int a, b;
            cin >> a >> b;
            a--, b--;
            g[a].pb({b, i});
            g[b].pb({a, i});
            ans[i] = -1;
        } else if (c == 'Q') {
            int a, d;
            cin >> a >> d;
            a--, d--;
            need1[d].pb({a, i});
            ans[i] = INF + 1;
        } else {
            int d;
            cin >> d;
            d--;
            need2[d].pb(i);
        }
    }
    zhfs(0, -1);
    solve(find_centroid(0, -1, n));
    for (int i = 0; i < n + k - 1; i++) {
        if (ans[i] == -1) continue;
        if (ans[i] >= INF) {
            if (ans[i] == INF) {
                cout << "yes\n";
            } else {
                cout << "no\n";
            }
        } else {
            cout << ans[i] << endl;
        }
    }
    return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 23892 KB Output is correct
2 Correct 43 ms 24072 KB Output is correct
3 Correct 46 ms 25164 KB Output is correct
4 Correct 45 ms 25476 KB Output is correct
5 Correct 47 ms 25748 KB Output is correct
6 Correct 47 ms 25420 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 23892 KB Output is correct
2 Correct 43 ms 24072 KB Output is correct
3 Correct 46 ms 25164 KB Output is correct
4 Correct 45 ms 25476 KB Output is correct
5 Correct 47 ms 25748 KB Output is correct
6 Correct 47 ms 25420 KB Output is correct
7 Correct 60 ms 24592 KB Output is correct
8 Correct 131 ms 24744 KB Output is correct
9 Correct 206 ms 24532 KB Output is correct
10 Correct 117 ms 24780 KB Output is correct
11 Correct 123 ms 25044 KB Output is correct
12 Correct 491 ms 24740 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 23824 KB Output is correct
2 Correct 144 ms 30248 KB Output is correct
3 Correct 145 ms 33100 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 23824 KB Output is correct
2 Correct 144 ms 30248 KB Output is correct
3 Correct 145 ms 33100 KB Output is correct
4 Correct 42 ms 24244 KB Output is correct
5 Execution timed out 3546 ms 32356 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 23892 KB Output is correct
2 Correct 245 ms 35968 KB Output is correct
3 Correct 230 ms 39300 KB Output is correct
4 Correct 177 ms 39368 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 23892 KB Output is correct
2 Correct 245 ms 35968 KB Output is correct
3 Correct 230 ms 39300 KB Output is correct
4 Correct 177 ms 39368 KB Output is correct
5 Correct 49 ms 24692 KB Output is correct
6 Correct 360 ms 39428 KB Output is correct
7 Correct 3166 ms 39700 KB Output is correct
8 Correct 386 ms 38532 KB Output is correct
9 Correct 335 ms 38544 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 23816 KB Output is correct
2 Correct 154 ms 29820 KB Output is correct
3 Correct 187 ms 32688 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 23816 KB Output is correct
2 Correct 154 ms 29820 KB Output is correct
3 Correct 187 ms 32688 KB Output is correct
4 Correct 38 ms 24660 KB Output is correct
5 Execution timed out 3555 ms 32968 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 23884 KB Output is correct
2 Correct 237 ms 35960 KB Output is correct
3 Correct 284 ms 39304 KB Output is correct
4 Correct 193 ms 39436 KB Output is correct
5 Correct 33 ms 24664 KB Output is correct
6 Correct 182 ms 33092 KB Output is correct
7 Correct 254 ms 32732 KB Output is correct
8 Correct 206 ms 33724 KB Output is correct
9 Correct 239 ms 33368 KB Output is correct
10 Correct 240 ms 36540 KB Output is correct
11 Correct 240 ms 35548 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 23884 KB Output is correct
2 Correct 237 ms 35960 KB Output is correct
3 Correct 284 ms 39304 KB Output is correct
4 Correct 193 ms 39436 KB Output is correct
5 Correct 33 ms 24664 KB Output is correct
6 Correct 182 ms 33092 KB Output is correct
7 Correct 254 ms 32732 KB Output is correct
8 Correct 206 ms 33724 KB Output is correct
9 Correct 239 ms 33368 KB Output is correct
10 Correct 240 ms 36540 KB Output is correct
11 Correct 240 ms 35548 KB Output is correct
12 Correct 39 ms 24652 KB Output is correct
13 Correct 309 ms 39384 KB Output is correct
14 Correct 3197 ms 39680 KB Output is correct
15 Correct 368 ms 38472 KB Output is correct
16 Correct 362 ms 38492 KB Output is correct
17 Correct 39 ms 24652 KB Output is correct
18 Correct 3307 ms 33216 KB Output is correct
19 Correct 268 ms 32676 KB Output is correct
20 Correct 308 ms 33640 KB Output is correct
21 Correct 282 ms 33716 KB Output is correct
22 Correct 1207 ms 35532 KB Output is correct
23 Execution timed out 3564 ms 35852 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 23892 KB Output is correct
2 Correct 39 ms 23984 KB Output is correct
3 Correct 40 ms 25192 KB Output is correct
4 Correct 46 ms 25432 KB Output is correct
5 Correct 47 ms 25652 KB Output is correct
6 Correct 44 ms 25496 KB Output is correct
7 Correct 31 ms 24780 KB Output is correct
8 Correct 144 ms 33032 KB Output is correct
9 Correct 148 ms 33064 KB Output is correct
10 Correct 36 ms 24780 KB Output is correct
11 Correct 228 ms 39256 KB Output is correct
12 Correct 221 ms 39304 KB Output is correct
13 Correct 161 ms 39508 KB Output is correct
14 Correct 31 ms 24796 KB Output is correct
15 Correct 161 ms 33000 KB Output is correct
16 Correct 176 ms 32788 KB Output is correct
17 Correct 190 ms 33532 KB Output is correct
18 Correct 203 ms 33388 KB Output is correct
19 Correct 239 ms 36556 KB Output is correct
20 Correct 226 ms 35500 KB Output is correct
21 Correct 157 ms 33172 KB Output is correct
22 Correct 224 ms 33156 KB Output is correct
23 Correct 160 ms 32904 KB Output is correct
24 Correct 161 ms 33192 KB Output is correct
25 Correct 247 ms 36412 KB Output is correct
26 Correct 213 ms 31904 KB Output is correct
27 Correct 194 ms 31820 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 23892 KB Output is correct
2 Correct 39 ms 23984 KB Output is correct
3 Correct 40 ms 25192 KB Output is correct
4 Correct 46 ms 25432 KB Output is correct
5 Correct 47 ms 25652 KB Output is correct
6 Correct 44 ms 25496 KB Output is correct
7 Correct 31 ms 24780 KB Output is correct
8 Correct 144 ms 33032 KB Output is correct
9 Correct 148 ms 33064 KB Output is correct
10 Correct 36 ms 24780 KB Output is correct
11 Correct 228 ms 39256 KB Output is correct
12 Correct 221 ms 39304 KB Output is correct
13 Correct 161 ms 39508 KB Output is correct
14 Correct 31 ms 24796 KB Output is correct
15 Correct 161 ms 33000 KB Output is correct
16 Correct 176 ms 32788 KB Output is correct
17 Correct 190 ms 33532 KB Output is correct
18 Correct 203 ms 33388 KB Output is correct
19 Correct 239 ms 36556 KB Output is correct
20 Correct 226 ms 35500 KB Output is correct
21 Correct 157 ms 33172 KB Output is correct
22 Correct 224 ms 33156 KB Output is correct
23 Correct 160 ms 32904 KB Output is correct
24 Correct 161 ms 33192 KB Output is correct
25 Correct 247 ms 36412 KB Output is correct
26 Correct 213 ms 31904 KB Output is correct
27 Correct 194 ms 31820 KB Output is correct
28 Correct 39 ms 24676 KB Output is correct
29 Correct 109 ms 24740 KB Output is correct
30 Correct 192 ms 24648 KB Output is correct
31 Correct 113 ms 24840 KB Output is correct
32 Correct 113 ms 24948 KB Output is correct
33 Correct 468 ms 24820 KB Output is correct
34 Correct 40 ms 24676 KB Output is correct
35 Correct 3456 ms 32740 KB Output is correct
36 Execution timed out 3568 ms 29632 KB Time limit exceeded
37 Halted 0 ms 0 KB -