oj.uz

Submission #846880

# Submission time Handle Problem Language Result Execution time Memory
846880 2023-09-08T15:18:53 Z Ahmed57 Inside information (BOI21_servers) C++17
50 / 100
 466 ms 130580 KB 
#include <bits/stdc++.h>
using namespace std;
int NODES=0;
bool seg[40000000];int L[40000000],R[40000000],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;
    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 '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 176 ms 6896 KB Output is correct
2 Correct 192 ms 8996 KB Output is correct
3 Correct 190 ms 8924 KB Output is correct
4 Correct 187 ms 8996 KB Output is correct
5 Correct 189 ms 8948 KB Output is correct
6 Correct 189 ms 9052 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 176 ms 6896 KB Output is correct
2 Correct 192 ms 8996 KB Output is correct
3 Correct 190 ms 8924 KB Output is correct
4 Correct 187 ms 8996 KB Output is correct
5 Correct 189 ms 8948 KB Output is correct
6 Correct 189 ms 9052 KB Output is correct
7 Incorrect 11 ms 7000 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 178 ms 6884 KB Output is correct
2 Correct 361 ms 46160 KB Output is correct
3 Correct 389 ms 46128 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 178 ms 6884 KB Output is correct
2 Correct 361 ms 46160 KB Output is correct
3 Correct 389 ms 46128 KB Output is correct
4 Incorrect 10 ms 7080 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 170 ms 6740 KB Output is correct
2 Correct 360 ms 52324 KB Output is correct
3 Correct 372 ms 52300 KB Output is correct
4 Correct 314 ms 46016 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 6740 KB Output is correct
2 Correct 360 ms 52324 KB Output is correct
3 Correct 372 ms 52300 KB Output is correct
4 Correct 314 ms 46016 KB Output is correct
5 Incorrect 9 ms 7004 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 170 ms 6932 KB Output is correct
2 Correct 374 ms 113404 KB Output is correct
3 Correct 373 ms 54168 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 6932 KB Output is correct
2 Correct 374 ms 113404 KB Output is correct
3 Correct 373 ms 54168 KB Output is correct
4 Incorrect 9 ms 7004 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 173 ms 6716 KB Output is correct
2 Correct 340 ms 52232 KB Output is correct
3 Correct 361 ms 52340 KB Output is correct
4 Correct 316 ms 46060 KB Output is correct
5 Correct 179 ms 7044 KB Output is correct
6 Correct 365 ms 112072 KB Output is correct
7 Correct 395 ms 54396 KB Output is correct
8 Correct 369 ms 54272 KB Output is correct
9 Correct 413 ms 54144 KB Output is correct
10 Correct 415 ms 60876 KB Output is correct
11 Correct 437 ms 63044 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 173 ms 6716 KB Output is correct
2 Correct 340 ms 52232 KB Output is correct
3 Correct 361 ms 52340 KB Output is correct
4 Correct 316 ms 46060 KB Output is correct
5 Correct 179 ms 7044 KB Output is correct
6 Correct 365 ms 112072 KB Output is correct
7 Correct 395 ms 54396 KB Output is correct
8 Correct 369 ms 54272 KB Output is correct
9 Correct 413 ms 54144 KB Output is correct
10 Correct 415 ms 60876 KB Output is correct
11 Correct 437 ms 63044 KB Output is correct
12 Incorrect 9 ms 7004 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 178 ms 7120 KB Output is correct
2 Correct 193 ms 8896 KB Output is correct
3 Correct 193 ms 8908 KB Output is correct
4 Correct 190 ms 8992 KB Output is correct
5 Correct 188 ms 8948 KB Output is correct
6 Correct 199 ms 9204 KB Output is correct
7 Correct 181 ms 6924 KB Output is correct
8 Correct 367 ms 46356 KB Output is correct
9 Correct 396 ms 46304 KB Output is correct
10 Correct 169 ms 6744 KB Output is correct
11 Correct 352 ms 52292 KB Output is correct
12 Correct 363 ms 52288 KB Output is correct
13 Correct 320 ms 46032 KB Output is correct
14 Correct 198 ms 6924 KB Output is correct
15 Correct 417 ms 111856 KB Output is correct
16 Correct 390 ms 54440 KB Output is correct
17 Correct 379 ms 54096 KB Output is correct
18 Correct 397 ms 54736 KB Output is correct
19 Correct 419 ms 60892 KB Output is correct
20 Correct 423 ms 62788 KB Output is correct
21 Correct 409 ms 48564 KB Output is correct
22 Correct 392 ms 54472 KB Output is correct
23 Correct 413 ms 56352 KB Output is correct
24 Correct 404 ms 56400 KB Output is correct
25 Correct 419 ms 48400 KB Output is correct
26 Correct 466 ms 124240 KB Output is correct
27 Correct 452 ms 130580 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 178 ms 7120 KB Output is correct
2 Correct 193 ms 8896 KB Output is correct
3 Correct 193 ms 8908 KB Output is correct
4 Correct 190 ms 8992 KB Output is correct
5 Correct 188 ms 8948 KB Output is correct
6 Correct 199 ms 9204 KB Output is correct
7 Correct 181 ms 6924 KB Output is correct
8 Correct 367 ms 46356 KB Output is correct
9 Correct 396 ms 46304 KB Output is correct
10 Correct 169 ms 6744 KB Output is correct
11 Correct 352 ms 52292 KB Output is correct
12 Correct 363 ms 52288 KB Output is correct
13 Correct 320 ms 46032 KB Output is correct
14 Correct 198 ms 6924 KB Output is correct
15 Correct 417 ms 111856 KB Output is correct
16 Correct 390 ms 54440 KB Output is correct
17 Correct 379 ms 54096 KB Output is correct
18 Correct 397 ms 54736 KB Output is correct
19 Correct 419 ms 60892 KB Output is correct
20 Correct 423 ms 62788 KB Output is correct
21 Correct 409 ms 48564 KB Output is correct
22 Correct 392 ms 54472 KB Output is correct
23 Correct 413 ms 56352 KB Output is correct
24 Correct 404 ms 56400 KB Output is correct
25 Correct 419 ms 48400 KB Output is correct
26 Correct 466 ms 124240 KB Output is correct
27 Correct 452 ms 130580 KB Output is correct
28 Incorrect 9 ms 7004 KB Extra information in the output file
29 Halted 0 ms 0 KB -