oj.uz

Submission #1090733

# Submission time Handle Problem Language Result Execution time Memory
1090733 2024-09-18T16:13:14 Z pokmui9909 Inside information (BOI21_servers) C++17
50 / 100
 257 ms 37060 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) 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) 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 19 ms 12432 KB Output is correct
2 Correct 31 ms 13920 KB Output is correct
3 Correct 27 ms 13136 KB Output is correct
4 Correct 35 ms 13980 KB Output is correct
5 Correct 33 ms 14164 KB Output is correct
6 Correct 28 ms 13856 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12432 KB Output is correct
2 Correct 31 ms 13920 KB Output is correct
3 Correct 27 ms 13136 KB Output is correct
4 Correct 35 ms 13980 KB Output is correct
5 Correct 33 ms 14164 KB Output is correct
6 Correct 28 ms 13856 KB Output is correct
7 Incorrect 21 ms 12464 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 12436 KB Output is correct
2 Correct 116 ms 35512 KB Output is correct
3 Correct 113 ms 35516 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 12436 KB Output is correct
2 Correct 116 ms 35512 KB Output is correct
3 Correct 113 ms 35516 KB Output is correct
4 Incorrect 21 ms 12472 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12436 KB Output is correct
2 Correct 251 ms 34372 KB Output is correct
3 Correct 257 ms 34380 KB Output is correct
4 Correct 171 ms 36808 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12436 KB Output is correct
2 Correct 251 ms 34372 KB Output is correct
3 Correct 257 ms 34380 KB Output is correct
4 Correct 171 ms 36808 KB Output is correct
5 Incorrect 21 ms 12472 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 12580 KB Output is correct
2 Correct 194 ms 30568 KB Output is correct
3 Correct 210 ms 27212 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 12580 KB Output is correct
2 Correct 194 ms 30568 KB Output is correct
3 Correct 210 ms 27212 KB Output is correct
4 Incorrect 21 ms 12460 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12580 KB Output is correct
2 Correct 246 ms 34380 KB Output is correct
3 Correct 239 ms 34464 KB Output is correct
4 Correct 171 ms 36836 KB Output is correct
5 Correct 19 ms 12440 KB Output is correct
6 Correct 186 ms 30544 KB Output is correct
7 Correct 195 ms 27208 KB Output is correct
8 Correct 221 ms 29140 KB Output is correct
9 Correct 215 ms 28384 KB Output is correct
10 Correct 242 ms 31196 KB Output is correct
11 Correct 233 ms 31896 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12580 KB Output is correct
2 Correct 246 ms 34380 KB Output is correct
3 Correct 239 ms 34464 KB Output is correct
4 Correct 171 ms 36836 KB Output is correct
5 Correct 19 ms 12440 KB Output is correct
6 Correct 186 ms 30544 KB Output is correct
7 Correct 195 ms 27208 KB Output is correct
8 Correct 221 ms 29140 KB Output is correct
9 Correct 215 ms 28384 KB Output is correct
10 Correct 242 ms 31196 KB Output is correct
11 Correct 233 ms 31896 KB Output is correct
12 Incorrect 22 ms 12472 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 12440 KB Output is correct
2 Correct 30 ms 13812 KB Output is correct
3 Correct 25 ms 13140 KB Output is correct
4 Correct 33 ms 13908 KB Output is correct
5 Correct 35 ms 14160 KB Output is correct
6 Correct 26 ms 13788 KB Output is correct
7 Correct 17 ms 12440 KB Output is correct
8 Correct 97 ms 35528 KB Output is correct
9 Correct 96 ms 35512 KB Output is correct
10 Correct 17 ms 12440 KB Output is correct
11 Correct 216 ms 34372 KB Output is correct
12 Correct 216 ms 34384 KB Output is correct
13 Correct 167 ms 37060 KB Output is correct
14 Correct 18 ms 12440 KB Output is correct
15 Correct 195 ms 30432 KB Output is correct
16 Correct 189 ms 27396 KB Output is correct
17 Correct 214 ms 29068 KB Output is correct
18 Correct 199 ms 28380 KB Output is correct
19 Correct 239 ms 31144 KB Output is correct
20 Correct 240 ms 31800 KB Output is correct
21 Correct 117 ms 36140 KB Output is correct
22 Correct 121 ms 33316 KB Output is correct
23 Correct 146 ms 28616 KB Output is correct
24 Correct 157 ms 28744 KB Output is correct
25 Correct 244 ms 36804 KB Output is correct
26 Correct 172 ms 26460 KB Output is correct
27 Correct 159 ms 26348 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 12440 KB Output is correct
2 Correct 30 ms 13812 KB Output is correct
3 Correct 25 ms 13140 KB Output is correct
4 Correct 33 ms 13908 KB Output is correct
5 Correct 35 ms 14160 KB Output is correct
6 Correct 26 ms 13788 KB Output is correct
7 Correct 17 ms 12440 KB Output is correct
8 Correct 97 ms 35528 KB Output is correct
9 Correct 96 ms 35512 KB Output is correct
10 Correct 17 ms 12440 KB Output is correct
11 Correct 216 ms 34372 KB Output is correct
12 Correct 216 ms 34384 KB Output is correct
13 Correct 167 ms 37060 KB Output is correct
14 Correct 18 ms 12440 KB Output is correct
15 Correct 195 ms 30432 KB Output is correct
16 Correct 189 ms 27396 KB Output is correct
17 Correct 214 ms 29068 KB Output is correct
18 Correct 199 ms 28380 KB Output is correct
19 Correct 239 ms 31144 KB Output is correct
20 Correct 240 ms 31800 KB Output is correct
21 Correct 117 ms 36140 KB Output is correct
22 Correct 121 ms 33316 KB Output is correct
23 Correct 146 ms 28616 KB Output is correct
24 Correct 157 ms 28744 KB Output is correct
25 Correct 244 ms 36804 KB Output is correct
26 Correct 172 ms 26460 KB Output is correct
27 Correct 159 ms 26348 KB Output is correct
28 Incorrect 19 ms 12288 KB Extra information in the output file
29 Halted 0 ms 0 KB -