oj.uz

Submission #560262

# Submission time Handle Problem Language Result Execution time Memory
560262 2022-05-11T08:18:26 Z Ooops_sorry Inside information (BOI21_servers) C++14
0 / 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 = 1.2e5 + 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
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 12768 KB Output is correct
2 Runtime error 75 ms 24280 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 25 ms 12768 KB Output is correct
2 Runtime error 75 ms 24280 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

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

Subtask #4
0 / 2.5

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

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 12952 KB Output is correct
2 Execution timed out 3530 ms 17888 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 12952 KB Output is correct
2 Execution timed out 3530 ms 17888 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 13040 KB Output is correct
2 Runtime error 2533 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 29 ms 13040 KB Output is correct
2 Runtime error 2533 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 26 ms 13028 KB Output is correct
2 Execution timed out 3532 ms 17940 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

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

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 13028 KB Output is correct
2 Runtime error 74 ms 23248 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 13028 KB Output is correct
2 Runtime error 74 ms 23248 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -