oj.uz

Submission #497084

# Submission time Handle Problem Language Result Execution time Memory
497084 2021-12-22T10:47:17 Z sudheerays123 Experimental Charges (NOI19_charges) C++
32 / 100
 1000 ms 8116 KB 
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long int
#define tc ll test;cin >> test;while(test--)
#define vi vector<ll>
#define pll pair<ll,ll>
#define pb push_back
#define mp make_pair
#define INF 1e18
#define MOD 1000000007
#define ff first
#define ss second
#define in >>
#define out <<
#define space << " " <<
#define spacef << " "
#define fo(i,a,b) for(ll i = a; i <= b; i++)
#define nextline out "\n"
#define print(x) for(auto i : x ) cout out i spacef
#define mmax(x,i) x = max(x,i)
#define mmin(x,i) x = min(x,i)
#define N 100005

vector<bool> visited(N,false);
vi color(N,-1);
vector<pll> adj[N];

void dfs(ll s , ll c){

    if(visited[s]) return;
    visited[s] = true;

    color[s] = c;

    for(auto u : adj[s]){
        if(u.second == 1) dfs(u.first,c == 1 ? 0 : 1);
        else dfs(u.first,c);
    }
}

int main() {
    
    fast;

    ll n,q;
    cin in n in q;

    while(q--){
        char x;
        ll a,b;
        
        cin in x in a in b;

        if(x == 'A'){
            adj[a].pb(mp(b,1));
            adj[b].pb(mp(a,1));
        }
        else if(x == 'R'){
            adj[a].pb(mp(b,0));
            adj[b].pb(mp(a,0));
        }
        else{
            fo(i,1,n){
                visited[i] = false;
                color[i] = -1;
            }

            dfs(a,0);
            
            if(color[b] == -1) cout out "?\n";
            else if(color[b] == 0) cout out "R\n";
            else cout out "A\n";
        }
    }

    return 0;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1048 ms 5140 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1095 ms 6932 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1074 ms 8116 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3408 KB Output is correct
2 Correct 2 ms 3408 KB Output is correct
3 Correct 2 ms 3408 KB Output is correct
4 Correct 2 ms 3408 KB Output is correct
5 Correct 2 ms 3408 KB Output is correct
6 Correct 6 ms 3476 KB Output is correct
7 Correct 6 ms 3484 KB Output is correct
8 Correct 3 ms 3488 KB Output is correct
9 Correct 5 ms 3476 KB Output is correct
10 Correct 3 ms 3484 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3408 KB Output is correct
2 Correct 2 ms 3408 KB Output is correct
3 Correct 2 ms 3408 KB Output is correct
4 Correct 2 ms 3408 KB Output is correct
5 Correct 2 ms 3408 KB Output is correct
6 Execution timed out 1048 ms 5140 KB Time limit exceeded
7 Halted 0 ms 0 KB -