Submission #560289

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
560289	2022-05-11T08:53:19 Z	Ooops_sorry	Inside information (BOI21_servers)	C++14	67.5 / 100	3500 ms	36860 KB

servers

#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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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	-

Submission #560289

Compilation message