oj.uz

Submission #560288

# Submission time Handle Problem Language Result Execution time Memory
560288 2022-05-11T08:51:21 Z Ooops_sorry Inside information (BOI21_servers) C++14
50 / 100
 321 ms 36412 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], arr, mas;
vector<bool> used(N), good(N);

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 walk(int v, int p) {
    if (!good[v]) return;
    mas.pb(v);
    for (auto to : g[v]) {
        if (to.first != p && !used[to.first]) {
            walk(to.first, v);
        }
    }
}

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;
        if (last == INF) {
            ans[to] += arr.size();
        } else {
            for (auto u : mas) {
                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));
            if (last == INF) {
                walk(to.first, v);
            }
        }
    }
}

void solve(int v) {
    sort(g[v].begin(), g[v].end(), [&](pair<int,int> a, pair<int,int> b){return a.second > b.second;});
    zhfs(v, -1);
    arr.clear();
    dfs1(v, -1, -INF, INF);
    mas.clear();
    mas.pb(v);
    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 23820 KB Output is correct
2 Correct 39 ms 24056 KB Output is correct
3 Correct 40 ms 23876 KB Output is correct
4 Correct 42 ms 24140 KB Output is correct
5 Correct 41 ms 24360 KB Output is correct
6 Correct 38 ms 24148 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 23820 KB Output is correct
2 Correct 39 ms 24056 KB Output is correct
3 Correct 40 ms 23876 KB Output is correct
4 Correct 42 ms 24140 KB Output is correct
5 Correct 41 ms 24360 KB Output is correct
6 Correct 38 ms 24148 KB Output is correct
7 Incorrect 56 ms 23736 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 30 ms 23916 KB Output is correct
2 Correct 160 ms 30716 KB Output is correct
3 Correct 140 ms 30712 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 23916 KB Output is correct
2 Correct 160 ms 30716 KB Output is correct
3 Correct 140 ms 30712 KB Output is correct
4 Incorrect 38 ms 23756 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 30 ms 23884 KB Output is correct
2 Correct 248 ms 35972 KB Output is correct
3 Correct 215 ms 35996 KB Output is correct
4 Correct 185 ms 36408 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 23884 KB Output is correct
2 Correct 248 ms 35972 KB Output is correct
3 Correct 215 ms 35996 KB Output is correct
4 Correct 185 ms 36408 KB Output is correct
5 Incorrect 41 ms 23804 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 31 ms 23892 KB Output is correct
2 Correct 165 ms 30152 KB Output is correct
3 Correct 202 ms 29416 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 23892 KB Output is correct
2 Correct 165 ms 30152 KB Output is correct
3 Correct 202 ms 29416 KB Output is correct
4 Incorrect 43 ms 23764 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 30 ms 23768 KB Output is correct
2 Correct 219 ms 36076 KB Output is correct
3 Correct 210 ms 35972 KB Output is correct
4 Correct 222 ms 36412 KB Output is correct
5 Correct 32 ms 23884 KB Output is correct
6 Correct 160 ms 30032 KB Output is correct
7 Correct 185 ms 29464 KB Output is correct
8 Correct 196 ms 30260 KB Output is correct
9 Correct 194 ms 30160 KB Output is correct
10 Correct 321 ms 33384 KB Output is correct
11 Correct 250 ms 32332 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 23768 KB Output is correct
2 Correct 219 ms 36076 KB Output is correct
3 Correct 210 ms 35972 KB Output is correct
4 Correct 222 ms 36412 KB Output is correct
5 Correct 32 ms 23884 KB Output is correct
6 Correct 160 ms 30032 KB Output is correct
7 Correct 185 ms 29464 KB Output is correct
8 Correct 196 ms 30260 KB Output is correct
9 Correct 194 ms 30160 KB Output is correct
10 Correct 321 ms 33384 KB Output is correct
11 Correct 250 ms 32332 KB Output is correct
12 Incorrect 40 ms 23896 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 31 ms 23884 KB Output is correct
2 Correct 41 ms 23984 KB Output is correct
3 Correct 38 ms 23884 KB Output is correct
4 Correct 41 ms 24116 KB Output is correct
5 Correct 38 ms 24352 KB Output is correct
6 Correct 39 ms 24080 KB Output is correct
7 Correct 30 ms 23892 KB Output is correct
8 Correct 152 ms 30668 KB Output is correct
9 Correct 142 ms 30652 KB Output is correct
10 Correct 30 ms 23772 KB Output is correct
11 Correct 251 ms 36072 KB Output is correct
12 Correct 222 ms 35976 KB Output is correct
13 Correct 184 ms 36408 KB Output is correct
14 Correct 36 ms 23812 KB Output is correct
15 Correct 166 ms 29972 KB Output is correct
16 Correct 195 ms 29548 KB Output is correct
17 Correct 193 ms 30276 KB Output is correct
18 Correct 201 ms 30056 KB Output is correct
19 Correct 298 ms 33336 KB Output is correct
20 Correct 261 ms 32308 KB Output is correct
21 Correct 166 ms 30100 KB Output is correct
22 Correct 171 ms 30028 KB Output is correct
23 Correct 176 ms 29760 KB Output is correct
24 Correct 159 ms 29772 KB Output is correct
25 Correct 283 ms 33484 KB Output is correct
26 Correct 206 ms 28600 KB Output is correct
27 Correct 205 ms 28408 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 23884 KB Output is correct
2 Correct 41 ms 23984 KB Output is correct
3 Correct 38 ms 23884 KB Output is correct
4 Correct 41 ms 24116 KB Output is correct
5 Correct 38 ms 24352 KB Output is correct
6 Correct 39 ms 24080 KB Output is correct
7 Correct 30 ms 23892 KB Output is correct
8 Correct 152 ms 30668 KB Output is correct
9 Correct 142 ms 30652 KB Output is correct
10 Correct 30 ms 23772 KB Output is correct
11 Correct 251 ms 36072 KB Output is correct
12 Correct 222 ms 35976 KB Output is correct
13 Correct 184 ms 36408 KB Output is correct
14 Correct 36 ms 23812 KB Output is correct
15 Correct 166 ms 29972 KB Output is correct
16 Correct 195 ms 29548 KB Output is correct
17 Correct 193 ms 30276 KB Output is correct
18 Correct 201 ms 30056 KB Output is correct
19 Correct 298 ms 33336 KB Output is correct
20 Correct 261 ms 32308 KB Output is correct
21 Correct 166 ms 30100 KB Output is correct
22 Correct 171 ms 30028 KB Output is correct
23 Correct 176 ms 29760 KB Output is correct
24 Correct 159 ms 29772 KB Output is correct
25 Correct 283 ms 33484 KB Output is correct
26 Correct 206 ms 28600 KB Output is correct
27 Correct 205 ms 28408 KB Output is correct
28 Incorrect 43 ms 23796 KB Extra information in the output file
29 Halted 0 ms 0 KB -