oj.uz

Submission #560263

# Submission time Handle Problem Language Result Execution time Memory
560263 2022-05-11T08:20:11 Z Ooops_sorry Inside information (BOI21_servers) C++14
5 / 100
 3500 ms 524288 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] && val[to.first] < to.second && first_val < fir[to.first]) {
            ans[to.second] = INF;
        }
    }
    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);
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) good[j] = 0;
        dfs1(i, -1, -INF, INF);
        for (auto to : need1[i]) {
            if (good[to.first] && val[to.first] < to.second) {
                ans[to.second] = INF;
            }
        }
        for (auto to : need2[i]) {
            int res = 0;
            for (int j = 0; j < n; j++) {
                if (good[j] && val[j] < to) {
                    res++;
                }
            }
            ans[to] = res;
        }
    }
    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 36 ms 24224 KB Output is correct
2 Correct 100 ms 24524 KB Output is correct
3 Correct 88 ms 29208 KB Output is correct
4 Correct 69 ms 25616 KB Output is correct
5 Correct 72 ms 25692 KB Output is correct
6 Correct 260 ms 57956 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 24224 KB Output is correct
2 Correct 100 ms 24524 KB Output is correct
3 Correct 88 ms 29208 KB Output is correct
4 Correct 69 ms 25616 KB Output is correct
5 Correct 72 ms 25692 KB Output is correct
6 Correct 260 ms 57956 KB Output is correct
7 Correct 41 ms 24688 KB Output is correct
8 Correct 390 ms 24984 KB Output is correct
9 Correct 749 ms 32656 KB Output is correct
10 Correct 364 ms 24988 KB Output is correct
11 Correct 325 ms 25032 KB Output is correct
12 Correct 903 ms 57240 KB Output is correct

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 40 ms 24240 KB Output is correct
2 Execution timed out 3532 ms 524288 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 40 ms 24240 KB Output is correct
2 Execution timed out 3532 ms 524288 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 23892 KB Output is correct
2 Execution timed out 3590 ms 28672 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 23892 KB Output is correct
2 Execution timed out 3590 ms 28672 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 23868 KB Output is correct
2 Runtime error 2410 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 23868 KB Output is correct
2 Runtime error 2410 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 23888 KB Output is correct
2 Execution timed out 3592 ms 28736 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 23888 KB Output is correct
2 Execution timed out 3592 ms 28736 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 23812 KB Output is correct
2 Correct 65 ms 24340 KB Output is correct
3 Correct 105 ms 28188 KB Output is correct
4 Correct 73 ms 25576 KB Output is correct
5 Correct 101 ms 25688 KB Output is correct
6 Correct 238 ms 58080 KB Output is correct
7 Correct 34 ms 24760 KB Output is correct
8 Execution timed out 3579 ms 345144 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 23812 KB Output is correct
2 Correct 65 ms 24340 KB Output is correct
3 Correct 105 ms 28188 KB Output is correct
4 Correct 73 ms 25576 KB Output is correct
5 Correct 101 ms 25688 KB Output is correct
6 Correct 238 ms 58080 KB Output is correct
7 Correct 34 ms 24760 KB Output is correct
8 Execution timed out 3579 ms 345144 KB Time limit exceeded
9 Halted 0 ms 0 KB -