oj.uz

Submission #560295

# Submission time Handle Problem Language Result Execution time Memory
560295 2022-05-11T09:01:04 Z Ooops_sorry Inside information (BOI21_servers) C++14
100 / 100
 687 ms 40860 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);

struct Fenwick {
    vector<int> t;
    Fenwick(int n) {
        t.resize(n);
    }
    void inc(int i, int d) {
        for (; i < t.size(); i = (i | (i + 1))) {
            t[i] += d;
        }
    }
    int get(int r) {
        int ans = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1) {
            ans += t[r];
        }
        return ans;
    }
} t(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;
    t.inc(val[v], 1);
    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;
        ans[to] += t.get(to - 1) + 1;
    }
}

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);
    dfs2(v, -1, INF, -INF);
    for (auto to : mas) {
        t.inc(val[to], -1);
    }
    mas.clear();
    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;
}

Compilation message

servers.cpp: In member function 'void Fenwick::inc(int, int)':
servers.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         for (; i < t.size(); i = (i | (i + 1))) {
      |                ~~^~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 24788 KB Output is correct
2 Correct 39 ms 25020 KB Output is correct
3 Correct 39 ms 24888 KB Output is correct
4 Correct 40 ms 25060 KB Output is correct
5 Correct 47 ms 25292 KB Output is correct
6 Correct 44 ms 25064 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 24788 KB Output is correct
2 Correct 39 ms 25020 KB Output is correct
3 Correct 39 ms 24888 KB Output is correct
4 Correct 40 ms 25060 KB Output is correct
5 Correct 47 ms 25292 KB Output is correct
6 Correct 44 ms 25064 KB Output is correct
7 Correct 39 ms 24820 KB Output is correct
8 Correct 123 ms 24656 KB Output is correct
9 Correct 140 ms 24528 KB Output is correct
10 Correct 119 ms 24632 KB Output is correct
11 Correct 110 ms 24892 KB Output is correct
12 Correct 121 ms 24868 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 24788 KB Output is correct
2 Correct 162 ms 31672 KB Output is correct
3 Correct 154 ms 31680 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 33 ms 24788 KB Output is correct
2 Correct 162 ms 31672 KB Output is correct
3 Correct 154 ms 31680 KB Output is correct
4 Correct 43 ms 24728 KB Output is correct
5 Correct 200 ms 31448 KB Output is correct
6 Correct 247 ms 30340 KB Output is correct
7 Correct 261 ms 31988 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 24824 KB Output is correct
2 Correct 232 ms 36940 KB Output is correct
3 Correct 275 ms 36960 KB Output is correct
4 Correct 223 ms 37388 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 24824 KB Output is correct
2 Correct 232 ms 36940 KB Output is correct
3 Correct 275 ms 36960 KB Output is correct
4 Correct 223 ms 37388 KB Output is correct
5 Correct 41 ms 24816 KB Output is correct
6 Correct 351 ms 37312 KB Output is correct
7 Correct 312 ms 37852 KB Output is correct
8 Correct 393 ms 36896 KB Output is correct
9 Correct 359 ms 36816 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 24780 KB Output is correct
2 Correct 223 ms 31024 KB Output is correct
3 Correct 197 ms 30512 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 24780 KB Output is correct
2 Correct 223 ms 31024 KB Output is correct
3 Correct 197 ms 30512 KB Output is correct
4 Correct 41 ms 24800 KB Output is correct
5 Correct 304 ms 31516 KB Output is correct
6 Correct 318 ms 30788 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 24844 KB Output is correct
2 Correct 286 ms 37008 KB Output is correct
3 Correct 267 ms 36944 KB Output is correct
4 Correct 260 ms 37364 KB Output is correct
5 Correct 33 ms 24776 KB Output is correct
6 Correct 205 ms 31020 KB Output is correct
7 Correct 236 ms 30412 KB Output is correct
8 Correct 259 ms 31272 KB Output is correct
9 Correct 270 ms 31060 KB Output is correct
10 Correct 438 ms 34348 KB Output is correct
11 Correct 348 ms 33268 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 24844 KB Output is correct
2 Correct 286 ms 37008 KB Output is correct
3 Correct 267 ms 36944 KB Output is correct
4 Correct 260 ms 37364 KB Output is correct
5 Correct 33 ms 24776 KB Output is correct
6 Correct 205 ms 31020 KB Output is correct
7 Correct 236 ms 30412 KB Output is correct
8 Correct 259 ms 31272 KB Output is correct
9 Correct 270 ms 31060 KB Output is correct
10 Correct 438 ms 34348 KB Output is correct
11 Correct 348 ms 33268 KB Output is correct
12 Correct 46 ms 24812 KB Output is correct
13 Correct 397 ms 37308 KB Output is correct
14 Correct 351 ms 37852 KB Output is correct
15 Correct 464 ms 36812 KB Output is correct
16 Correct 446 ms 36852 KB Output is correct
17 Correct 58 ms 24772 KB Output is correct
18 Correct 347 ms 31424 KB Output is correct
19 Correct 345 ms 30776 KB Output is correct
20 Correct 353 ms 31660 KB Output is correct
21 Correct 421 ms 31636 KB Output is correct
22 Correct 562 ms 33728 KB Output is correct
23 Correct 687 ms 34432 KB Output is correct
24 Correct 636 ms 36976 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 45 ms 24868 KB Output is correct
2 Correct 54 ms 25028 KB Output is correct
3 Correct 44 ms 24860 KB Output is correct
4 Correct 53 ms 25036 KB Output is correct
5 Correct 69 ms 25232 KB Output is correct
6 Correct 53 ms 25120 KB Output is correct
7 Correct 54 ms 24824 KB Output is correct
8 Correct 243 ms 31624 KB Output is correct
9 Correct 211 ms 31680 KB Output is correct
10 Correct 45 ms 24776 KB Output is correct
11 Correct 353 ms 36948 KB Output is correct
12 Correct 380 ms 36956 KB Output is correct
13 Correct 278 ms 37404 KB Output is correct
14 Correct 41 ms 24776 KB Output is correct
15 Correct 286 ms 31024 KB Output is correct
16 Correct 313 ms 30444 KB Output is correct
17 Correct 294 ms 31260 KB Output is correct
18 Correct 347 ms 31088 KB Output is correct
19 Correct 465 ms 34316 KB Output is correct
20 Correct 396 ms 33284 KB Output is correct
21 Correct 205 ms 31260 KB Output is correct
22 Correct 221 ms 31032 KB Output is correct
23 Correct 215 ms 30672 KB Output is correct
24 Correct 227 ms 30668 KB Output is correct
25 Correct 334 ms 34556 KB Output is correct
26 Correct 247 ms 29472 KB Output is correct
27 Correct 297 ms 29380 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 45 ms 24868 KB Output is correct
2 Correct 54 ms 25028 KB Output is correct
3 Correct 44 ms 24860 KB Output is correct
4 Correct 53 ms 25036 KB Output is correct
5 Correct 69 ms 25232 KB Output is correct
6 Correct 53 ms 25120 KB Output is correct
7 Correct 54 ms 24824 KB Output is correct
8 Correct 243 ms 31624 KB Output is correct
9 Correct 211 ms 31680 KB Output is correct
10 Correct 45 ms 24776 KB Output is correct
11 Correct 353 ms 36948 KB Output is correct
12 Correct 380 ms 36956 KB Output is correct
13 Correct 278 ms 37404 KB Output is correct
14 Correct 41 ms 24776 KB Output is correct
15 Correct 286 ms 31024 KB Output is correct
16 Correct 313 ms 30444 KB Output is correct
17 Correct 294 ms 31260 KB Output is correct
18 Correct 347 ms 31088 KB Output is correct
19 Correct 465 ms 34316 KB Output is correct
20 Correct 396 ms 33284 KB Output is correct
21 Correct 205 ms 31260 KB Output is correct
22 Correct 221 ms 31032 KB Output is correct
23 Correct 215 ms 30672 KB Output is correct
24 Correct 227 ms 30668 KB Output is correct
25 Correct 334 ms 34556 KB Output is correct
26 Correct 247 ms 29472 KB Output is correct
27 Correct 297 ms 29380 KB Output is correct
28 Correct 40 ms 24788 KB Output is correct
29 Correct 118 ms 24656 KB Output is correct
30 Correct 109 ms 24420 KB Output is correct
31 Correct 123 ms 24692 KB Output is correct
32 Correct 126 ms 24908 KB Output is correct
33 Correct 109 ms 24620 KB Output is correct
34 Correct 45 ms 24780 KB Output is correct
35 Correct 176 ms 31460 KB Output is correct
36 Correct 232 ms 30260 KB Output is correct
37 Correct 265 ms 32068 KB Output is correct
38 Correct 41 ms 25680 KB Output is correct
39 Correct 316 ms 40500 KB Output is correct
40 Correct 325 ms 40860 KB Output is correct
41 Correct 386 ms 39492 KB Output is correct
42 Correct 397 ms 39500 KB Output is correct
43 Correct 41 ms 25624 KB Output is correct
44 Correct 319 ms 34416 KB Output is correct
45 Correct 291 ms 33668 KB Output is correct
46 Correct 302 ms 34568 KB Output is correct
47 Correct 335 ms 34576 KB Output is correct
48 Correct 430 ms 36384 KB Output is correct
49 Correct 535 ms 37316 KB Output is correct
50 Correct 389 ms 36976 KB Output is correct
51 Correct 268 ms 32828 KB Output is correct
52 Correct 279 ms 32832 KB Output is correct
53 Correct 236 ms 32388 KB Output is correct
54 Correct 250 ms 33092 KB Output is correct
55 Correct 269 ms 32092 KB Output is correct
56 Correct 236 ms 33028 KB Output is correct
57 Correct 335 ms 35392 KB Output is correct
58 Correct 401 ms 33264 KB Output is correct
59 Correct 298 ms 32972 KB Output is correct