oj.uz

Submission #388544

# Submission time Handle Problem Language Result Execution time Memory
388544 2021-04-12T04:26:35 Z strawberry2005 Experimental Charges (NOI19_charges) C++17
32 / 100
 30 ms 3988 KB 
#include<bits/stdc++.h>

using namespace std;

#define int long long
const int mod = 1e9+7;
#define deb(x) cout<<#x<<": "<<x<<endl

int iceil(int a, int b) {
  return (a + b - 1) / b;
}

vector<int> parent1,parent2,done;

int find_ds(int x){
    if(parent1[x]==x) return(x);
    return(parent1[x]=find_ds(parent1[x]));
}

void union_ds(int a,int b){
    a=find_ds(a);b=find_ds(b);
    if(a!=b) parent1[b]=a;
}

int find_ds2(int x){
    if(parent2[x]==x) return(x);
    return(parent2[x]=find_ds2(parent2[x]));
}

void union_ds2(int a,int b){
    a=find_ds2(a);b=find_ds2(b);
    if(a!=b) parent2[b]=a;
}


signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.precision(20);

    #ifdef strawberryshaker2005
        freopen("input.txt", "r", stdin);
    #endif

    int n,k;
    cin>>n>>k;
    parent1.resize(n);done.assign(n,0);parent2.resize(n);
    for(int i=0;i<n;i++) parent1[i]=i;
    for(int i=0;i<n;i++) parent2[i]=i;
    for(int i=0;i<k;i++){
        char a;int b,c;
        cin>>a>>b>>c;b--;c--;
        if(a=='Q'){
            if(done[b]==0||done[c]==0) cout<<"?\n";
            else{
                if(find_ds(b)==find_ds(c)) cout<<"R\n";
                else if(find_ds2(b)==find_ds2(c)) cout<<"A\n";
                else cout<<"?\n";
            }
        }
        else if(a=='R'){
            union_ds(b,c);done[b]=1;done[c]=1;
        }
        else{
            done[b]=1;done[c]=1;
            union_ds2(b,c);
        }
    } 



    return(0);
    
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3436 KB Output is correct
2 Correct 22 ms 3456 KB Output is correct
3 Correct 27 ms 3532 KB Output is correct
4 Correct 28 ms 3484 KB Output is correct
5 Correct 24 ms 3476 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3964 KB Output is correct
2 Correct 28 ms 3928 KB Output is correct
3 Correct 27 ms 3884 KB Output is correct
4 Correct 30 ms 3900 KB Output is correct
5 Correct 30 ms 3988 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 3908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Incorrect 1 ms 332 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 27 ms 3436 KB Output is correct
7 Correct 22 ms 3456 KB Output is correct
8 Correct 27 ms 3532 KB Output is correct
9 Correct 28 ms 3484 KB Output is correct
10 Correct 24 ms 3476 KB Output is correct
11 Correct 25 ms 3964 KB Output is correct
12 Correct 28 ms 3928 KB Output is correct
13 Correct 27 ms 3884 KB Output is correct
14 Correct 30 ms 3900 KB Output is correct
15 Correct 30 ms 3988 KB Output is correct
16 Incorrect 25 ms 3908 KB Output isn't correct
17 Halted 0 ms 0 KB -