제출 #487550

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
487550		sudheerays123	Experimental Charges (NOI19_charges)	C++98	32 / 100	46 ms	11140 KiB

charges

#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

vi parent(N);

void make_set(ll n){
    fo(i,1,n) parent[i] = i;
}

ll find(ll x){
    if(x == parent[x]) return x;
    return parent[x] = find(parent[x]); 
}

void add_edge(ll a , ll b){
    
    a = find(a);
    b = find(b);

    if(a != b) parent[b] = a;
}

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(!visited[u.first]){

            if(u.second == 0) dfs(u.first,c);
            else{
                if(c == 1) dfs(u.first,0);
                else dfs(u.first,1);
            }
        }
    }
}

int main() {
    
    fast;

    ll n,m;
    cin in n in m;

    make_set(n);

    vi ans;
    vector<pll> q;
 
    fo(i,1,m){
        char x;
        ll a,b;
        
        cin in x in a in b;

        if(x == 'Q'){
            if(find(a) != find(b)) ans.pb(0);
            else{
                ans.pb(1);
                q.pb(mp(a,b));
            }
        }
        else if(x == 'R'){
            add_edge(a,b);
            adj[a].pb(mp(b,0));
            adj[b].pb(mp(a,0));
        }
        else{
            add_edge(a,b);
            adj[a].pb(mp(b,1));
            adj[b].pb(mp(a,1));
        }
    }

    fo(i,1,n) if(!visited[i]) dfs(1,0);

    ll ind = 0;
    vector<char> answer;

    for(auto u : ans){
        if(u == 0) answer.pb('?');
        if(u == 1){
            ll a = q[ind].first , b = q[ind].second;

            if(find(a) != find(b)) answer.pb('?');
            else if(color[a] == color[b]) answer.pb('R');
            else answer.pb('A');

            ind++;
        }
    }

    for(auto u : answer) cout out u nextline;

    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 14 / 14
• Subtask 4: 0 / 12
• Subtask 5: 0 / 25
• Subtask 6: 0 / 31