oj.uz

Submission #560258

# Submission time Handle Problem Language Result Execution time Memory
560258 2022-05-11T08:15:21 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], need[N];
vector<int> sz(N), ans(N), val(N), fir(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 : need[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--;
            need[d].pb({a, i});
        } else {
            int d;
            cin >> d;
            d--;
            assert(0);
        }
    }
    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 : need[i]) {
            if (good[to.first] && val[to.first] < to.second) {
                ans[to.second] = INF;
            }
        }
    }
    for (int i = 0; i < n + k - 1; i++) {
        if (ans[i] == -1) continue;
        if (ans[i] == INF) {
            cout << "yes\n";
        } else {
            cout << "no\n";
        }
    }
    return 0;
}

Subtask #1
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 9796 KB Output is correct
2 Correct 62 ms 11612 KB Output is correct
3 Runtime error 92 ms 18176 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 9796 KB Output is correct
2 Correct 62 ms 11612 KB Output is correct
3 Runtime error 92 ms 18176 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 26 ms 9844 KB Output is correct
2 Runtime error 3444 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 26 ms 9844 KB Output is correct
2 Runtime error 3444 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 27 ms 9916 KB Output is correct
2 Execution timed out 3589 ms 17912 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 9916 KB Output is correct
2 Execution timed out 3589 ms 17912 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 9920 KB Output is correct
2 Runtime error 2375 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 26 ms 9920 KB Output is correct
2 Runtime error 2375 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 24 ms 9940 KB Output is correct
2 Execution timed out 3541 ms 18172 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 24 ms 9940 KB Output is correct
2 Execution timed out 3541 ms 18172 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 9948 KB Output is correct
2 Correct 67 ms 11588 KB Output is correct
3 Runtime error 85 ms 18128 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 9948 KB Output is correct
2 Correct 67 ms 11588 KB Output is correct
3 Runtime error 85 ms 18128 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -