oj.uz

Submission #846881

# Submission time Handle Problem Language Result Execution time Memory
846881 2023-09-08T15:21:35 Z Ahmed57 Inside information (BOI21_servers) C++17
52.5 / 100
 826 ms 132688 KB 
#include <bits/stdc++.h>
using namespace std;
int NODES=0;
bool seg[44000007];int L[44000007],R[44000007],n;
void update(int p, int q, int l, int r, int x)
{
    if(l==r){seg[p]=1;return;}
    int md = (l+r)/2;
    seg[p]=1;
    if(x<=md)R[p]=R[q],L[p]=++NODES,update(L[p],L[q],l,md,x);
    else L[p]=L[q],R[p]=++NODES,update(R[p],R[q],md+1,r,x);
}
bool query(int p,int l,int r,int x){
    if(l==r){
        return seg[p];
    }
    int md=(l+r)/2;
    if(x<=md)return query(L[p],l,md,x);
    else return query(R[p],md+1,r,x);
}
vector<int> v;
void iterate(int p,int l,int r){
    if(!seg[p])return;
    if(l==r)v.push_back(l);
    else{
        int md=(l+r)/2;
        iterate(L[p],l,md);
        iterate(R[p],md+1,r);
    }
}
int pr[125001];
int gs[125001];
void merg(int a,int b){
    if(gs[a]>gs[b])swap(a,b);
    iterate(pr[a],1,n);int tm;
    for(auto x:v){
        tm = ++NODES;
        update(tm,pr[b],1,n,x);
        pr[b]=tm;
    }
    pr[a]=tm,pr[b]=tm,gs[b]+=gs[a],gs[a]=gs[b];
    v.clear();
}
int main(){
    int q;cin>>n>>q;
    if(n<=4000){
        vector<int> v[n+1];
    for(int i = 1;i<=n;i++)v[i].push_back(i);
    int cnt[n+1] = {0};
    for(int i = 1;i<=n;i++)cnt[i] = 1;
    q+=n-1;
    while(q--){
        char s;cin>>s;
        if(s=='S'){
            int a,b;cin>>a>>b;
            set<int> x;
            for(auto i:v[a]){x.insert(i);cnt[i]--;}
            for(auto i:v[b]){x.insert(i);cnt[i]--;}
            v[a].clear();v[b].clear();
            for(auto i:x){
                v[a].push_back(i);
                v[b].push_back(i);
                cnt[i]+=2;
            }
        }else if(s=='C'){
            int a;cin>>a;
            cout<<cnt[a]<<endl;
        }else{
            int a,b;cin>>a>>b;
            auto it = lower_bound(v[a].begin(),v[a].end(),b)-v[a].begin();
            if(it==v[a].size()||v[a][it]!=b)cout<<"no\n";
            else cout<<"yes\n";
        }
    }
    return 0;
    }
    for(int i = 1;i<=n;i++){
        pr[i] = ++NODES , gs[i] = 1;
    }
    for(int i = 1;i<=n;i++){
        int tm = ++NODES;
        update(tm,pr[i],1,n,i);
        pr[i]=tm;
    }
    q+=n-1;
    while(q--){
        char c;cin>>c;
        if(c=='S'){int a,b;cin>>a>>b;merg(a,b);}
        else{
            int a,b;cin>>a>>b;
            cout<<(query(pr[a],1,n,b)?"yes\n":"no\n");
        }
    }
}

Compilation message

servers.cpp: In function 'int main()':
servers.cpp:71:18: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |             if(it==v[a].size()||v[a][it]!=b)cout<<"no\n";
      |                ~~^~~~~~~~~~~~~
servers.cpp: In function 'void merg(int, int)':
servers.cpp:41:10: warning: 'tm' may be used uninitialized in this function [-Wmaybe-uninitialized]
   41 |     pr[a]=tm,pr[b]=tm,gs[b]+=gs[a],gs[a]=gs[b];
      |     ~~~~~^~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 180 ms 2896 KB Output is correct
2 Correct 201 ms 3152 KB Output is correct
3 Correct 272 ms 8800 KB Output is correct
4 Correct 189 ms 3092 KB Output is correct
5 Correct 195 ms 3100 KB Output is correct
6 Correct 819 ms 43556 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 180 ms 2896 KB Output is correct
2 Correct 201 ms 3152 KB Output is correct
3 Correct 272 ms 8800 KB Output is correct
4 Correct 189 ms 3092 KB Output is correct
5 Correct 195 ms 3100 KB Output is correct
6 Correct 819 ms 43556 KB Output is correct
7 Correct 187 ms 2640 KB Output is correct
8 Correct 180 ms 2948 KB Output is correct
9 Correct 275 ms 10592 KB Output is correct
10 Correct 180 ms 2896 KB Output is correct
11 Correct 178 ms 2828 KB Output is correct
12 Correct 804 ms 43564 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 176 ms 2848 KB Output is correct
2 Correct 378 ms 44336 KB Output is correct
3 Correct 424 ms 44528 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 176 ms 2848 KB Output is correct
2 Correct 378 ms 44336 KB Output is correct
3 Correct 424 ms 44528 KB Output is correct
4 Correct 174 ms 2640 KB Output is correct
5 Incorrect 24 ms 26148 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 2604 KB Output is correct
2 Correct 378 ms 52124 KB Output is correct
3 Correct 341 ms 52260 KB Output is correct
4 Correct 303 ms 43980 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 2604 KB Output is correct
2 Correct 378 ms 52124 KB Output is correct
3 Correct 341 ms 52260 KB Output is correct
4 Correct 303 ms 43980 KB Output is correct
5 Correct 171 ms 2792 KB Output is correct
6 Incorrect 24 ms 25804 KB Extra information in the output file
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 2764 KB Output is correct
2 Correct 379 ms 111876 KB Output is correct
3 Correct 373 ms 52316 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 2764 KB Output is correct
2 Correct 379 ms 111876 KB Output is correct
3 Correct 373 ms 52316 KB Output is correct
4 Correct 177 ms 2664 KB Output is correct
5 Incorrect 24 ms 25944 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 173 ms 2800 KB Output is correct
2 Correct 374 ms 52176 KB Output is correct
3 Correct 384 ms 52320 KB Output is correct
4 Correct 311 ms 44080 KB Output is correct
5 Correct 181 ms 2824 KB Output is correct
6 Correct 375 ms 111952 KB Output is correct
7 Correct 397 ms 52404 KB Output is correct
8 Correct 414 ms 52580 KB Output is correct
9 Correct 387 ms 52160 KB Output is correct
10 Correct 399 ms 62924 KB Output is correct
11 Correct 437 ms 62668 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 173 ms 2800 KB Output is correct
2 Correct 374 ms 52176 KB Output is correct
3 Correct 384 ms 52320 KB Output is correct
4 Correct 311 ms 44080 KB Output is correct
5 Correct 181 ms 2824 KB Output is correct
6 Correct 375 ms 111952 KB Output is correct
7 Correct 397 ms 52404 KB Output is correct
8 Correct 414 ms 52580 KB Output is correct
9 Correct 387 ms 52160 KB Output is correct
10 Correct 399 ms 62924 KB Output is correct
11 Correct 437 ms 62668 KB Output is correct
12 Correct 176 ms 2640 KB Output is correct
13 Incorrect 25 ms 25888 KB Extra information in the output file
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 170 ms 2760 KB Output is correct
2 Correct 187 ms 3144 KB Output is correct
3 Correct 267 ms 8788 KB Output is correct
4 Correct 193 ms 3060 KB Output is correct
5 Correct 190 ms 3416 KB Output is correct
6 Correct 826 ms 43304 KB Output is correct
7 Correct 178 ms 2872 KB Output is correct
8 Correct 387 ms 44176 KB Output is correct
9 Correct 398 ms 44112 KB Output is correct
10 Correct 174 ms 3088 KB Output is correct
11 Correct 376 ms 52444 KB Output is correct
12 Correct 347 ms 52308 KB Output is correct
13 Correct 313 ms 44112 KB Output is correct
14 Correct 171 ms 3000 KB Output is correct
15 Correct 379 ms 111952 KB Output is correct
16 Correct 403 ms 52304 KB Output is correct
17 Correct 401 ms 52392 KB Output is correct
18 Correct 399 ms 52576 KB Output is correct
19 Correct 425 ms 62924 KB Output is correct
20 Correct 450 ms 62768 KB Output is correct
21 Correct 398 ms 48220 KB Output is correct
22 Correct 452 ms 52408 KB Output is correct
23 Correct 423 ms 56460 KB Output is correct
24 Correct 434 ms 56400 KB Output is correct
25 Correct 395 ms 48208 KB Output is correct
26 Correct 478 ms 122716 KB Output is correct
27 Correct 462 ms 132688 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 170 ms 2760 KB Output is correct
2 Correct 187 ms 3144 KB Output is correct
3 Correct 267 ms 8788 KB Output is correct
4 Correct 193 ms 3060 KB Output is correct
5 Correct 190 ms 3416 KB Output is correct
6 Correct 826 ms 43304 KB Output is correct
7 Correct 178 ms 2872 KB Output is correct
8 Correct 387 ms 44176 KB Output is correct
9 Correct 398 ms 44112 KB Output is correct
10 Correct 174 ms 3088 KB Output is correct
11 Correct 376 ms 52444 KB Output is correct
12 Correct 347 ms 52308 KB Output is correct
13 Correct 313 ms 44112 KB Output is correct
14 Correct 171 ms 3000 KB Output is correct
15 Correct 379 ms 111952 KB Output is correct
16 Correct 403 ms 52304 KB Output is correct
17 Correct 401 ms 52392 KB Output is correct
18 Correct 399 ms 52576 KB Output is correct
19 Correct 425 ms 62924 KB Output is correct
20 Correct 450 ms 62768 KB Output is correct
21 Correct 398 ms 48220 KB Output is correct
22 Correct 452 ms 52408 KB Output is correct
23 Correct 423 ms 56460 KB Output is correct
24 Correct 434 ms 56400 KB Output is correct
25 Correct 395 ms 48208 KB Output is correct
26 Correct 478 ms 122716 KB Output is correct
27 Correct 462 ms 132688 KB Output is correct
28 Correct 189 ms 3052 KB Output is correct
29 Correct 181 ms 4104 KB Output is correct
30 Correct 283 ms 11760 KB Output is correct
31 Correct 182 ms 4176 KB Output is correct
32 Correct 184 ms 4164 KB Output is correct
33 Correct 805 ms 44472 KB Output is correct
34 Correct 176 ms 3596 KB Output is correct
35 Incorrect 27 ms 25748 KB Extra information in the output file
36 Halted 0 ms 0 KB -