oj.uz

Submission #1090741

# Submission time Handle Problem Language Result Execution time Memory
1090741 2024-09-18T16:17:27 Z pokmui9909 Inside information (BOI21_servers) C++17
100 / 100
 655 ms 59124 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define x first
#define y second

ll N, K;
vector<pair<ll, ll>> T[120005];
ll S[120005], vis[120005], Ans[120005];
struct Query{
    ll v, t, n;
    bool operator< (const Query &r) const{
        return t < r.t;
    }
};
vector<Query> Qry[120005];

struct Fen{
    ll T[120005];
    void upd(ll k, ll v) { while(k <= N) T[k] += v, k += k & -k; }
    ll qry(ll k) { ll r = 0; while(k >= 1) r += T[k], k -= k & -k; return r; }
}seg;

ll Size(ll u, ll p){
    S[u] = 1;
    for(auto e : T[u]){
        if(e.x != p && !vis[e.x]) S[u] += Size(e.x, u);
    }
    return S[u];
}
ll Cent(ll u, ll p, ll n){
    for(auto e : T[u]){
        if(e.x != p && !vis[e.x] && S[e.x] > n / 2) return Cent(e.x, u, n);
    }
    return u;
}

ll Num[120005], X[120005], Y[120005], Z[120005];
void dfs(ll u, ll p, ll pc, vector<ll> &V, ll n){
    V.push_back(u); Num[u] = n;
    for(auto e : T[u]){
        if(e.x == p || vis[e.x]) continue;
        X[e.x] = -1, Y[e.x] = -1, Z[e.x] = min(Z[u], e.y);
        if(X[u] != -1 && pc > e.y) X[e.x] = X[u];
        if(Y[u] != -1 && pc < e.y) Y[e.x] = e.y;
        dfs(e.x, u, e.y, V, n);
    }
}

void dnc(ll _u){
    ll c = Cent(_u, -1, Size(_u, -1));
    vis[c] = 1;
    vector<vector<ll>> Sub;
    Sub.push_back({c});
    X[c] = 1, Y[c] = 0, Z[c] = N, Num[c] = c;
    for(auto e : T[c]){
        if(vis[e.x]) continue;
        X[e.x] = Y[e.x] = Z[e.x] = e.y;
        Sub.push_back({});
        dfs(e.x, -1, e.y, Sub.back(), e.x);
    }
    vector<Query> Q;
    vector<pair<ll, ll>> V, His;
    for(ll i = 0; i < Sub.size(); i++){
        for(auto u : Sub[i]){
            if(Y[u] != -1) V.push_back({Y[u], Z[u]});
            for(auto q : Qry[u]){
                if(q.v == -1){
                    Q.push_back({u, q.t, q.n});
                } else if(Num[q.v] != 0 && Num[u] != Num[q.v] && Y[u] != -1 && Y[u] <= q.t && X[q.v] != -1 && X[q.v] <= q.t && Z[u] >= X[q.v]){
                    Ans[q.n] = -99;
                }
            }
        }
    }

    sort(Q.begin(), Q.end()); sort(V.begin(), V.end());
    for(ll i = 0, j = 0; i < Q.size(); i++){
        while(j < V.size() && V[j].x <= Q[i].t){
            seg.upd(V[j].y, 1); His.push_back({V[j].y, 1});
            j++;
        }
        if(X[Q[i].v] != -1 && X[Q[i].v] <= Q[i].t) Ans[Q[i].n] += seg.qry(N) - seg.qry(X[Q[i].v] - 1);
    }
    for(auto t : His) seg.upd(t.x, -t.y);

    for(ll k = 0; k < Sub.size(); k++){
        Q.clear(); V.clear(); His.clear();
        for(auto u : Sub[k]){
            if(Y[u] != -1) V.push_back({Y[u], Z[u]});
            for(auto q : Qry[u]){
                if(q.v == -1) Q.push_back({u, q.t, q.n});
            }
            
            Num[u] = 0;
        }
        sort(Q.begin(), Q.end()); sort(V.begin(), V.end());
        for(ll i = 0, j = 0; i < Q.size(); i++){
            while(j < V.size() && V[j].x <= Q[i].t){
                seg.upd(V[j].y, 1); His.push_back({V[j].y, 1});
                j++;
            }
            if(X[Q[i].v] != -1 && X[Q[i].v] <= Q[i].t) Ans[Q[i].n] -= seg.qry(N) - seg.qry(X[Q[i].v] - 1);
        }
        for(auto t : His) seg.upd(t.x, -t.y);
    }

    for(auto e : T[c]){
        if(vis[e.x]) continue;
        dnc(e.x);
    }
}

int main(){
    cin.tie(0) -> sync_with_stdio(0);

    cin >> N >> K;
    ll t = 0;
    for(ll i = 1; i <= N + K - 1; i++){
        char op; ll u, v; cin >> op >> u;
        if(op == 'S'){
            cin >> v; t++;
            T[u].push_back({v, t});
            T[v].push_back({u, t});
        } else if(op == 'Q'){
            cin >> v;
            if(u == v){
                Ans[i - t] = -99; continue; 
            }
            Qry[u].push_back({v, t, i - t});
            Ans[i - t] = -100;
        } else {
            Qry[u].push_back({-1, t, i - t});
        }
    }
    dnc(1);
    for(ll i = 1; i <= K; i++){
        if(Ans[i] < 0){
            cout << (Ans[i] == -100 ? "no\n" : "yes\n");
        } else {
            cout << Ans[i] + 1 << '\n';
        }
    }
}

Compilation message

servers.cpp: In function 'void dnc(ll)':
servers.cpp:65:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(ll i = 0; i < Sub.size(); i++){
      |                   ~~^~~~~~~~~~~~
servers.cpp:79:28: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(ll i = 0, j = 0; i < Q.size(); i++){
      |                          ~~^~~~~~~~~~
servers.cpp:80:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         while(j < V.size() && V[j].x <= Q[i].t){
      |               ~~^~~~~~~~~~
servers.cpp:88:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for(ll k = 0; k < Sub.size(); k++){
      |                   ~~^~~~~~~~~~~~
servers.cpp:99:32: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         for(ll i = 0, j = 0; i < Q.size(); i++){
      |                              ~~^~~~~~~~~~
servers.cpp:100:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |             while(j < V.size() && V[j].x <= Q[i].t){
      |                   ~~^~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 12436 KB Output is correct
2 Correct 32 ms 13908 KB Output is correct
3 Correct 28 ms 13156 KB Output is correct
4 Correct 38 ms 13916 KB Output is correct
5 Correct 64 ms 14168 KB Output is correct
6 Correct 31 ms 13776 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 12436 KB Output is correct
2 Correct 32 ms 13908 KB Output is correct
3 Correct 28 ms 13156 KB Output is correct
4 Correct 38 ms 13916 KB Output is correct
5 Correct 64 ms 14168 KB Output is correct
6 Correct 31 ms 13776 KB Output is correct
7 Correct 21 ms 12464 KB Output is correct
8 Correct 74 ms 16340 KB Output is correct
9 Correct 46 ms 16008 KB Output is correct
10 Correct 105 ms 16692 KB Output is correct
11 Correct 71 ms 16848 KB Output is correct
12 Correct 33 ms 14352 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 12524 KB Output is correct
2 Correct 168 ms 35512 KB Output is correct
3 Correct 171 ms 35512 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 30 ms 12524 KB Output is correct
2 Correct 168 ms 35512 KB Output is correct
3 Correct 171 ms 35512 KB Output is correct
4 Correct 20 ms 12472 KB Output is correct
5 Correct 165 ms 38636 KB Output is correct
6 Correct 112 ms 38708 KB Output is correct
7 Correct 140 ms 39912 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12436 KB Output is correct
2 Correct 330 ms 34372 KB Output is correct
3 Correct 308 ms 34356 KB Output is correct
4 Correct 207 ms 36796 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12436 KB Output is correct
2 Correct 330 ms 34372 KB Output is correct
3 Correct 308 ms 34356 KB Output is correct
4 Correct 207 ms 36796 KB Output is correct
5 Correct 21 ms 12292 KB Output is correct
6 Correct 482 ms 38848 KB Output is correct
7 Correct 410 ms 41788 KB Output is correct
8 Correct 592 ms 41920 KB Output is correct
9 Correct 586 ms 41784 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12436 KB Output is correct
2 Correct 221 ms 30432 KB Output is correct
3 Correct 262 ms 27320 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12436 KB Output is correct
2 Correct 221 ms 30432 KB Output is correct
3 Correct 262 ms 27320 KB Output is correct
4 Correct 21 ms 12404 KB Output is correct
5 Correct 373 ms 36576 KB Output is correct
6 Correct 344 ms 31564 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12492 KB Output is correct
2 Correct 305 ms 34528 KB Output is correct
3 Correct 288 ms 34360 KB Output is correct
4 Correct 185 ms 36924 KB Output is correct
5 Correct 19 ms 12440 KB Output is correct
6 Correct 195 ms 30568 KB Output is correct
7 Correct 238 ms 27272 KB Output is correct
8 Correct 245 ms 29140 KB Output is correct
9 Correct 268 ms 28392 KB Output is correct
10 Correct 340 ms 31304 KB Output is correct
11 Correct 346 ms 32080 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12492 KB Output is correct
2 Correct 305 ms 34528 KB Output is correct
3 Correct 288 ms 34360 KB Output is correct
4 Correct 185 ms 36924 KB Output is correct
5 Correct 19 ms 12440 KB Output is correct
6 Correct 195 ms 30568 KB Output is correct
7 Correct 238 ms 27272 KB Output is correct
8 Correct 245 ms 29140 KB Output is correct
9 Correct 268 ms 28392 KB Output is correct
10 Correct 340 ms 31304 KB Output is correct
11 Correct 346 ms 32080 KB Output is correct
12 Correct 24 ms 12216 KB Output is correct
13 Correct 431 ms 38448 KB Output is correct
14 Correct 382 ms 41896 KB Output is correct
15 Correct 573 ms 41920 KB Output is correct
16 Correct 600 ms 41788 KB Output is correct
17 Correct 19 ms 12468 KB Output is correct
18 Correct 386 ms 36552 KB Output is correct
19 Correct 457 ms 31496 KB Output is correct
20 Correct 418 ms 32904 KB Output is correct
21 Correct 433 ms 32948 KB Output is correct
22 Correct 642 ms 39092 KB Output is correct
23 Correct 655 ms 37340 KB Output is correct
24 Correct 571 ms 34552 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 12512 KB Output is correct
2 Correct 40 ms 13828 KB Output is correct
3 Correct 50 ms 13140 KB Output is correct
4 Correct 43 ms 13908 KB Output is correct
5 Correct 45 ms 14124 KB Output is correct
6 Correct 33 ms 13780 KB Output is correct
7 Correct 32 ms 12480 KB Output is correct
8 Correct 181 ms 35472 KB Output is correct
9 Correct 175 ms 35540 KB Output is correct
10 Correct 19 ms 12492 KB Output is correct
11 Correct 323 ms 34376 KB Output is correct
12 Correct 306 ms 34456 KB Output is correct
13 Correct 190 ms 36792 KB Output is correct
14 Correct 20 ms 12428 KB Output is correct
15 Correct 176 ms 30548 KB Output is correct
16 Correct 222 ms 27244 KB Output is correct
17 Correct 245 ms 29124 KB Output is correct
18 Correct 201 ms 28276 KB Output is correct
19 Correct 222 ms 31060 KB Output is correct
20 Correct 238 ms 32088 KB Output is correct
21 Correct 126 ms 36104 KB Output is correct
22 Correct 130 ms 33448 KB Output is correct
23 Correct 142 ms 28752 KB Output is correct
24 Correct 176 ms 28740 KB Output is correct
25 Correct 335 ms 36732 KB Output is correct
26 Correct 215 ms 26424 KB Output is correct
27 Correct 257 ms 26340 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 22 ms 12512 KB Output is correct
2 Correct 40 ms 13828 KB Output is correct
3 Correct 50 ms 13140 KB Output is correct
4 Correct 43 ms 13908 KB Output is correct
5 Correct 45 ms 14124 KB Output is correct
6 Correct 33 ms 13780 KB Output is correct
7 Correct 32 ms 12480 KB Output is correct
8 Correct 181 ms 35472 KB Output is correct
9 Correct 175 ms 35540 KB Output is correct
10 Correct 19 ms 12492 KB Output is correct
11 Correct 323 ms 34376 KB Output is correct
12 Correct 306 ms 34456 KB Output is correct
13 Correct 190 ms 36792 KB Output is correct
14 Correct 20 ms 12428 KB Output is correct
15 Correct 176 ms 30548 KB Output is correct
16 Correct 222 ms 27244 KB Output is correct
17 Correct 245 ms 29124 KB Output is correct
18 Correct 201 ms 28276 KB Output is correct
19 Correct 222 ms 31060 KB Output is correct
20 Correct 238 ms 32088 KB Output is correct
21 Correct 126 ms 36104 KB Output is correct
22 Correct 130 ms 33448 KB Output is correct
23 Correct 142 ms 28752 KB Output is correct
24 Correct 176 ms 28740 KB Output is correct
25 Correct 335 ms 36732 KB Output is correct
26 Correct 215 ms 26424 KB Output is correct
27 Correct 257 ms 26340 KB Output is correct
28 Correct 21 ms 12200 KB Output is correct
29 Correct 90 ms 16484 KB Output is correct
30 Correct 45 ms 15832 KB Output is correct
31 Correct 103 ms 16828 KB Output is correct
32 Correct 63 ms 16848 KB Output is correct
33 Correct 53 ms 14344 KB Output is correct
34 Correct 18 ms 12472 KB Output is correct
35 Correct 150 ms 38816 KB Output is correct
36 Correct 104 ms 38796 KB Output is correct
37 Correct 122 ms 39992 KB Output is correct
38 Correct 19 ms 12472 KB Output is correct
39 Correct 407 ms 38592 KB Output is correct
40 Correct 374 ms 41924 KB Output is correct
41 Correct 565 ms 42024 KB Output is correct
42 Correct 571 ms 41920 KB Output is correct
43 Correct 23 ms 12456 KB Output is correct
44 Correct 367 ms 36460 KB Output is correct
45 Correct 423 ms 31540 KB Output is correct
46 Correct 391 ms 32972 KB Output is correct
47 Correct 393 ms 32860 KB Output is correct
48 Correct 551 ms 39112 KB Output is correct
49 Correct 639 ms 37284 KB Output is correct
50 Correct 491 ms 34376 KB Output is correct
51 Correct 170 ms 43124 KB Output is correct
52 Correct 151 ms 40184 KB Output is correct
53 Correct 142 ms 40348 KB Output is correct
54 Correct 134 ms 40012 KB Output is correct
55 Correct 171 ms 42268 KB Output is correct
56 Correct 245 ms 35348 KB Output is correct
57 Correct 393 ms 59124 KB Output is correct
58 Correct 420 ms 32972 KB Output is correct
59 Correct 251 ms 27736 KB Output is correct