oj.uz

답안 #560289

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
560289 2022-05-11T08:53:19 Z Ooops_sorry Inside information (BOI21_servers) C++14
67.5 / 100
 3500 ms 36860 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 : 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);
            }
        }
    }
    for (auto to : need2[v]) {
        if (first_val > to) continue;
        if (last == INF) {
            for (auto u : arr) {
                if (fir[u] > first_val && val[u] < to) {
                    ans[to]++;
                }
            }
        } else {
            for (auto u : mas) {
                if (fir[u] > first_val && val[u] < to) {
                    ans[to]++;
                }
            }
        }
    }
}

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

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 23828 KB Output is correct
2 Correct 40 ms 24036 KB Output is correct
3 Correct 37 ms 23896 KB Output is correct
4 Correct 42 ms 24112 KB Output is correct
5 Correct 39 ms 24268 KB Output is correct
6 Correct 42 ms 24096 KB Output is correct

Subtask #2
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 23828 KB Output is correct
2 Correct 40 ms 24036 KB Output is correct
3 Correct 37 ms 23896 KB Output is correct
4 Correct 42 ms 24112 KB Output is correct
5 Correct 39 ms 24268 KB Output is correct
6 Correct 42 ms 24096 KB Output is correct
7 Correct 38 ms 23844 KB Output is correct
8 Correct 108 ms 23644 KB Output is correct
9 Correct 171 ms 23436 KB Output is correct
10 Correct 118 ms 23704 KB Output is correct
11 Correct 109 ms 23916 KB Output is correct
12 Correct 409 ms 23644 KB Output is correct

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 23808 KB Output is correct
2 Correct 149 ms 30724 KB Output is correct
3 Correct 150 ms 30836 KB Output is correct

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 23808 KB Output is correct
2 Correct 149 ms 30724 KB Output is correct
3 Correct 150 ms 30836 KB Output is correct
4 Correct 39 ms 23776 KB Output is correct
5 Correct 2925 ms 30512 KB Output is correct
6 Execution timed out 3590 ms 30116 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 23768 KB Output is correct
2 Correct 239 ms 35972 KB Output is correct
3 Correct 242 ms 35980 KB Output is correct
4 Correct 170 ms 36392 KB Output is correct

Subtask #6
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 23768 KB Output is correct
2 Correct 239 ms 35972 KB Output is correct
3 Correct 242 ms 35980 KB Output is correct
4 Correct 170 ms 36392 KB Output is correct
5 Correct 41 ms 23780 KB Output is correct
6 Correct 323 ms 36348 KB Output is correct
7 Correct 3269 ms 36856 KB Output is correct
8 Correct 376 ms 35812 KB Output is correct
9 Correct 348 ms 35880 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 23840 KB Output is correct
2 Correct 173 ms 30008 KB Output is correct
3 Correct 181 ms 29468 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 23840 KB Output is correct
2 Correct 173 ms 30008 KB Output is correct
3 Correct 181 ms 29468 KB Output is correct
4 Correct 51 ms 23756 KB Output is correct
5 Correct 3097 ms 30512 KB Output is correct
6 Correct 274 ms 32716 KB Output is correct

Subtask #9
12.5 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 23808 KB Output is correct
2 Correct 244 ms 35916 KB Output is correct
3 Correct 215 ms 36024 KB Output is correct
4 Correct 196 ms 36424 KB Output is correct
5 Correct 30 ms 23844 KB Output is correct
6 Correct 168 ms 30044 KB Output is correct
7 Correct 207 ms 29508 KB Output is correct
8 Correct 207 ms 30232 KB Output is correct
9 Correct 205 ms 30116 KB Output is correct
10 Correct 313 ms 33288 KB Output is correct
11 Correct 250 ms 32304 KB Output is correct

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 23808 KB Output is correct
2 Correct 244 ms 35916 KB Output is correct
3 Correct 215 ms 36024 KB Output is correct
4 Correct 196 ms 36424 KB Output is correct
5 Correct 30 ms 23844 KB Output is correct
6 Correct 168 ms 30044 KB Output is correct
7 Correct 207 ms 29508 KB Output is correct
8 Correct 207 ms 30232 KB Output is correct
9 Correct 205 ms 30116 KB Output is correct
10 Correct 313 ms 33288 KB Output is correct
11 Correct 250 ms 32304 KB Output is correct
12 Correct 41 ms 23724 KB Output is correct
13 Correct 297 ms 36440 KB Output is correct
14 Correct 3257 ms 36860 KB Output is correct
15 Correct 353 ms 36020 KB Output is correct
16 Correct 362 ms 35860 KB Output is correct
17 Correct 40 ms 23784 KB Output is correct
18 Correct 2984 ms 30508 KB Output is correct
19 Correct 253 ms 29772 KB Output is correct
20 Correct 248 ms 30636 KB Output is correct
21 Correct 288 ms 30796 KB Output is correct
22 Correct 1169 ms 32796 KB Output is correct
23 Execution timed out 3575 ms 32936 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 23832 KB Output is correct
2 Correct 39 ms 24048 KB Output is correct
3 Correct 40 ms 23820 KB Output is correct
4 Correct 41 ms 24140 KB Output is correct
5 Correct 39 ms 24276 KB Output is correct
6 Correct 39 ms 24140 KB Output is correct
7 Correct 30 ms 23888 KB Output is correct
8 Correct 140 ms 30716 KB Output is correct
9 Correct 144 ms 30712 KB Output is correct
10 Correct 29 ms 23780 KB Output is correct
11 Correct 216 ms 36024 KB Output is correct
12 Correct 217 ms 35944 KB Output is correct
13 Correct 182 ms 36404 KB Output is correct
14 Correct 31 ms 23804 KB Output is correct
15 Correct 165 ms 30024 KB Output is correct
16 Correct 174 ms 29532 KB Output is correct
17 Correct 174 ms 30288 KB Output is correct
18 Correct 193 ms 30120 KB Output is correct
19 Correct 252 ms 33336 KB Output is correct
20 Correct 233 ms 32212 KB Output is correct
21 Correct 159 ms 30276 KB Output is correct
22 Correct 161 ms 30076 KB Output is correct
23 Correct 157 ms 29680 KB Output is correct
24 Correct 159 ms 29832 KB Output is correct
25 Correct 235 ms 33480 KB Output is correct
26 Correct 205 ms 28492 KB Output is correct
27 Correct 205 ms 28476 KB Output is correct

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 23832 KB Output is correct
2 Correct 39 ms 24048 KB Output is correct
3 Correct 40 ms 23820 KB Output is correct
4 Correct 41 ms 24140 KB Output is correct
5 Correct 39 ms 24276 KB Output is correct
6 Correct 39 ms 24140 KB Output is correct
7 Correct 30 ms 23888 KB Output is correct
8 Correct 140 ms 30716 KB Output is correct
9 Correct 144 ms 30712 KB Output is correct
10 Correct 29 ms 23780 KB Output is correct
11 Correct 216 ms 36024 KB Output is correct
12 Correct 217 ms 35944 KB Output is correct
13 Correct 182 ms 36404 KB Output is correct
14 Correct 31 ms 23804 KB Output is correct
15 Correct 165 ms 30024 KB Output is correct
16 Correct 174 ms 29532 KB Output is correct
17 Correct 174 ms 30288 KB Output is correct
18 Correct 193 ms 30120 KB Output is correct
19 Correct 252 ms 33336 KB Output is correct
20 Correct 233 ms 32212 KB Output is correct
21 Correct 159 ms 30276 KB Output is correct
22 Correct 161 ms 30076 KB Output is correct
23 Correct 157 ms 29680 KB Output is correct
24 Correct 159 ms 29832 KB Output is correct
25 Correct 235 ms 33480 KB Output is correct
26 Correct 205 ms 28492 KB Output is correct
27 Correct 205 ms 28476 KB Output is correct
28 Correct 39 ms 23836 KB Output is correct
29 Correct 108 ms 23624 KB Output is correct
30 Correct 167 ms 23636 KB Output is correct
31 Correct 108 ms 23684 KB Output is correct
32 Correct 108 ms 23836 KB Output is correct
33 Correct 414 ms 23656 KB Output is correct
34 Correct 38 ms 23868 KB Output is correct
35 Correct 2917 ms 30508 KB Output is correct
36 Execution timed out 3538 ms 28480 KB Time limit exceeded
37 Halted 0 ms 0 KB -