Submission #1090724

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090724		pokmui9909	Inside information (BOI21_servers)	C++17	0 / 100	21 ms	18840 KiB

servers

#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 && 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 (stderr)

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: 0 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 0 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 0 / 17.5
• Subtask 12: 0 / 17.5