oj.uz

Submission #812179

# Submission time Handle Problem Language Result Execution time Memory
812179 2023-08-07T07:42:35 Z alvingogo Inside information (BOI21_servers) C++14
100 / 100
 437 ms 33372 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

struct BIT{
    int n;
    vector<int> bt;
    void init(int x){
        n=x;
        bt.resize(n+1);
    }
    void update(int x,int y){
        x++;
        for(;x<=n;x+=(x&-x)){
            bt[x]+=y;
        }
    }
    int query(int x){
        x++;
        int ans=0;
        for(;x>0;x-=(x&-x)){
            ans+=bt[x];
        }
        return ans;
    }
}bt;

vector<int> ans;
struct no{
    vector<pair<int,int> > ch;
    int ab=0;
    int sz;
    int vis=0;
    vector<int> l;
    vector<pair<int,int> > r;
    int fa=-1;
};
vector<no> v;
void init(int x){
    v.resize(x);
}
int dfs(int r,int f,int n){
    v[r].sz=1;
    int s=-1;
    for(auto h:v[r].ch){
        if(!v[h.fs].vis && h.fs!=f){
            s=max(s,dfs(h.fs,r,n));
            v[r].sz+=v[h.fs].sz;
        }
    }
    if(s>=0){
        return s;
    }
    else if(v[r].sz>n/2){
        return r;
    }
    else{
        return -1;
    }
}
void dfs2(int r,int f){
    v[r].sz=1;
    v[r].fa=-1;
    for(auto h:v[r].ch){
        if(!v[h.fs].vis && h.fs!=f){
            dfs2(h.fs,r);
            v[r].sz+=v[h.fs].sz;
        }
    }
}
void dfs3(int r,int f,int z){
    for(auto h:v[r].l){
        ans[h]+=bt.query(h);
    }
    for(auto h:v[r].r){
        if(v[h.fs].fa>=0 && v[h.fs].fa<h.sc){
            ans[h.sc]=-2;
        }
    }
    for(auto h:v[r].ch){
        if(!v[h.fs].vis && h.fs!=f && h.sc<z){
            dfs3(h.fs,r,h.sc);
        }
    }
}
vector<int> g;
void dfs4(int r,int f,int z){
    g.push_back(z);
    v[r].fa=z;
    bt.update(z,1);
    for(auto h:v[r].ch){
        if(!v[h.fs].vis && h.fs!=f && h.sc>z){
            dfs4(h.fs,r,h.sc);
        }
    }
}
void dc(int r,int n){
    r=dfs(r,r,n);
    int m=v[r].ch.size();
    for(int i=m-1;i>=0;i--){
        auto h=v[r].ch[i];
        if(v[h.fs].vis){
            continue;
        }
        bt.update(h.sc,1);
        v[r].fa=h.sc;
        dfs3(h.fs,r,h.sc);
        dfs4(h.fs,r,h.sc);
        v[r].fa=-1;
        bt.update(h.sc,-1);
    }
    for(auto h:v[r].l){
        ans[h]+=bt.query(h)+1;
    }
    for(auto h:v[r].r){
        if(v[h.fs].fa>=0 && v[h.fs].fa<h.sc){
            ans[h.sc]=-2;
        }
    }
    while(g.size()){
        auto h=g.back();
        g.pop_back();
        bt.update(h,-1);
    }
    dfs2(r,r);
    v[r].vis=1;
    for(auto h:v[r].ch){
        if(!v[h.fs].vis){
            dc(h.fs,v[h.fs].sz);
        }
    }
}
int main(){
    AquA;
    int n,k;
    cin >> n >> k;
    int q=(n-1+k);
    vector<pair<int,pair<int,int> > > qr;
    bt.init(q+2);
    v.resize(n);
    ans.resize(q,0);
    for(int i=0;i<q;i++){
        char s;
        cin >> s;
        if(s=='S'){
            int a,b;
            cin >> a >> b;
            a--;
            b--;
            v[a].ch.push_back({b,i});
            v[b].ch.push_back({a,i});
            ans[i]=-3;
        }
        else if(s=='Q'){
            int a,b;
            cin >> a >> b;
            a--;
            b--;
            if(a==b){
                ans[i]=-2;
                continue;
            }
            v[b].r.push_back({a,i});
            ans[i]=-1;
        }
        else{
            int a;
            cin >> a;
            a--;
            v[a].l.push_back(i);
        }
    }
    dc(0,0);
    for(int i=0;i<q;i++){
        if(ans[i]!=-3){
            if(ans[i]<0){
                if(ans[i]==-1){
                    cout << "no\n";
                }
                else{
                    cout << "yes\n";
                }
            }
            else{
                cout << ans[i] << "\n";
            }
        }
    }
    return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3188 KB Output is correct
2 Correct 24 ms 3788 KB Output is correct
3 Correct 22 ms 3540 KB Output is correct
4 Correct 24 ms 3916 KB Output is correct
5 Correct 24 ms 4048 KB Output is correct
6 Correct 25 ms 3788 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3188 KB Output is correct
2 Correct 24 ms 3788 KB Output is correct
3 Correct 22 ms 3540 KB Output is correct
4 Correct 24 ms 3916 KB Output is correct
5 Correct 24 ms 4048 KB Output is correct
6 Correct 25 ms 3788 KB Output is correct
7 Correct 24 ms 3164 KB Output is correct
8 Correct 28 ms 3388 KB Output is correct
9 Correct 27 ms 3256 KB Output is correct
10 Correct 28 ms 3504 KB Output is correct
11 Correct 26 ms 3716 KB Output is correct
12 Correct 24 ms 3356 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3284 KB Output is correct
2 Correct 150 ms 24628 KB Output is correct
3 Correct 162 ms 24636 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3284 KB Output is correct
2 Correct 150 ms 24628 KB Output is correct
3 Correct 162 ms 24636 KB Output is correct
4 Correct 16 ms 4076 KB Output is correct
5 Correct 163 ms 24316 KB Output is correct
6 Correct 121 ms 21912 KB Output is correct
7 Correct 109 ms 22144 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3252 KB Output is correct
2 Correct 257 ms 28852 KB Output is correct
3 Correct 260 ms 28880 KB Output is correct
4 Correct 182 ms 32856 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3252 KB Output is correct
2 Correct 257 ms 28852 KB Output is correct
3 Correct 260 ms 28880 KB Output is correct
4 Correct 182 ms 32856 KB Output is correct
5 Correct 20 ms 3984 KB Output is correct
6 Correct 302 ms 32396 KB Output is correct
7 Correct 217 ms 33372 KB Output is correct
8 Correct 319 ms 31896 KB Output is correct
9 Correct 332 ms 31944 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3276 KB Output is correct
2 Correct 218 ms 24544 KB Output is correct
3 Correct 228 ms 23768 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3276 KB Output is correct
2 Correct 218 ms 24544 KB Output is correct
3 Correct 228 ms 23768 KB Output is correct
4 Correct 19 ms 4060 KB Output is correct
5 Correct 213 ms 24704 KB Output is correct
6 Correct 303 ms 23848 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3260 KB Output is correct
2 Correct 288 ms 28852 KB Output is correct
3 Correct 276 ms 28836 KB Output is correct
4 Correct 169 ms 32864 KB Output is correct
5 Correct 15 ms 4180 KB Output is correct
6 Correct 164 ms 24536 KB Output is correct
7 Correct 200 ms 23660 KB Output is correct
8 Correct 207 ms 25132 KB Output is correct
9 Correct 187 ms 24728 KB Output is correct
10 Correct 223 ms 28192 KB Output is correct
11 Correct 249 ms 27732 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3260 KB Output is correct
2 Correct 288 ms 28852 KB Output is correct
3 Correct 276 ms 28836 KB Output is correct
4 Correct 169 ms 32864 KB Output is correct
5 Correct 15 ms 4180 KB Output is correct
6 Correct 164 ms 24536 KB Output is correct
7 Correct 200 ms 23660 KB Output is correct
8 Correct 207 ms 25132 KB Output is correct
9 Correct 187 ms 24728 KB Output is correct
10 Correct 223 ms 28192 KB Output is correct
11 Correct 249 ms 27732 KB Output is correct
12 Correct 16 ms 4052 KB Output is correct
13 Correct 247 ms 32492 KB Output is correct
14 Correct 196 ms 33332 KB Output is correct
15 Correct 269 ms 31840 KB Output is correct
16 Correct 275 ms 31820 KB Output is correct
17 Correct 16 ms 4052 KB Output is correct
18 Correct 196 ms 24724 KB Output is correct
19 Correct 277 ms 23944 KB Output is correct
20 Correct 245 ms 25156 KB Output is correct
21 Correct 247 ms 24888 KB Output is correct
22 Correct 316 ms 28104 KB Output is correct
23 Correct 437 ms 27956 KB Output is correct
24 Correct 427 ms 27404 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3256 KB Output is correct
2 Correct 28 ms 3736 KB Output is correct
3 Correct 22 ms 3540 KB Output is correct
4 Correct 25 ms 3924 KB Output is correct
5 Correct 26 ms 4128 KB Output is correct
6 Correct 37 ms 3856 KB Output is correct
7 Correct 25 ms 3188 KB Output is correct
8 Correct 158 ms 24628 KB Output is correct
9 Correct 153 ms 24568 KB Output is correct
10 Correct 19 ms 4184 KB Output is correct
11 Correct 236 ms 32196 KB Output is correct
12 Correct 219 ms 32208 KB Output is correct
13 Correct 171 ms 32856 KB Output is correct
14 Correct 16 ms 4172 KB Output is correct
15 Correct 174 ms 24552 KB Output is correct
16 Correct 174 ms 23696 KB Output is correct
17 Correct 233 ms 25012 KB Output is correct
18 Correct 210 ms 24592 KB Output is correct
19 Correct 224 ms 28264 KB Output is correct
20 Correct 243 ms 27840 KB Output is correct
21 Correct 155 ms 24640 KB Output is correct
22 Correct 158 ms 24716 KB Output is correct
23 Correct 166 ms 24472 KB Output is correct
24 Correct 192 ms 24536 KB Output is correct
25 Correct 273 ms 28740 KB Output is correct
26 Correct 197 ms 22940 KB Output is correct
27 Correct 182 ms 22688 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3256 KB Output is correct
2 Correct 28 ms 3736 KB Output is correct
3 Correct 22 ms 3540 KB Output is correct
4 Correct 25 ms 3924 KB Output is correct
5 Correct 26 ms 4128 KB Output is correct
6 Correct 37 ms 3856 KB Output is correct
7 Correct 25 ms 3188 KB Output is correct
8 Correct 158 ms 24628 KB Output is correct
9 Correct 153 ms 24568 KB Output is correct
10 Correct 19 ms 4184 KB Output is correct
11 Correct 236 ms 32196 KB Output is correct
12 Correct 219 ms 32208 KB Output is correct
13 Correct 171 ms 32856 KB Output is correct
14 Correct 16 ms 4172 KB Output is correct
15 Correct 174 ms 24552 KB Output is correct
16 Correct 174 ms 23696 KB Output is correct
17 Correct 233 ms 25012 KB Output is correct
18 Correct 210 ms 24592 KB Output is correct
19 Correct 224 ms 28264 KB Output is correct
20 Correct 243 ms 27840 KB Output is correct
21 Correct 155 ms 24640 KB Output is correct
22 Correct 158 ms 24716 KB Output is correct
23 Correct 166 ms 24472 KB Output is correct
24 Correct 192 ms 24536 KB Output is correct
25 Correct 273 ms 28740 KB Output is correct
26 Correct 197 ms 22940 KB Output is correct
27 Correct 182 ms 22688 KB Output is correct
28 Correct 16 ms 3964 KB Output is correct
29 Correct 27 ms 4544 KB Output is correct
30 Correct 23 ms 4328 KB Output is correct
31 Correct 27 ms 4576 KB Output is correct
32 Correct 28 ms 4752 KB Output is correct
33 Correct 27 ms 4568 KB Output is correct
34 Correct 16 ms 3948 KB Output is correct
35 Correct 131 ms 24256 KB Output is correct
36 Correct 90 ms 21968 KB Output is correct
37 Correct 109 ms 22076 KB Output is correct
38 Correct 18 ms 3996 KB Output is correct
39 Correct 222 ms 32396 KB Output is correct
40 Correct 184 ms 33348 KB Output is correct
41 Correct 249 ms 31964 KB Output is correct
42 Correct 231 ms 31884 KB Output is correct
43 Correct 15 ms 4052 KB Output is correct
44 Correct 180 ms 24716 KB Output is correct
45 Correct 219 ms 23856 KB Output is correct
46 Correct 208 ms 25096 KB Output is correct
47 Correct 228 ms 24884 KB Output is correct
48 Correct 277 ms 28216 KB Output is correct
49 Correct 343 ms 27956 KB Output is correct
50 Correct 304 ms 27400 KB Output is correct
51 Correct 118 ms 22872 KB Output is correct
52 Correct 99 ms 22896 KB Output is correct
53 Correct 93 ms 22500 KB Output is correct
54 Correct 97 ms 23084 KB Output is correct
55 Correct 135 ms 22412 KB Output is correct
56 Correct 143 ms 23600 KB Output is correct
57 Correct 207 ms 26568 KB Output is correct
58 Correct 285 ms 23504 KB Output is correct
59 Correct 194 ms 22820 KB Output is correct