Submission #878702

#	Time	Username	Problem	Language	Result	Execution time	Memory
878702		Sir_Ahmed_Imran	One-Way Streets (CEOI17_oneway)	C++17	60 / 100	3056 ms	19028 KiB

oneway

                              ///~~~LOTA~~~///
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define li long int
#define ld long double
#define append push_back
#define add insert
#define nl "\n"
#define ff first
#define ss second
#define pii pair<int,int>
#define pic pair<int,char>
#define all(x) (x).begin(),(x).end()
#define sum(a) accumulate(all(a),0) 
#define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL)
#define terminator main
#define N 100001
char c[N];
int vis[N];
int cup[N];
int Par[N];
int par[N];
int cpar[N];
int dept[N];
pii edge[N];
vector<pii> a[N];
vector<pii> g[N];
int root(int v){
    if(!Par[v]) return v;
    Par[v]=root(Par[v]);
    return Par[v];
}
void merge(int v,int u){
    Par[root(u)]=root(v);
}
bool same(int v,int u){
    return (root(v)==root(u));
}
void dfs(int v){
    for(auto& i:a[v]){
        if(!dept[i.ff] || dept[i.ff]>dept[v])
            cup[v]--;
        else cup[v]++;
        if(!dept[i.ff]){
            dept[i.ff]=dept[v]+1;
            cpar[i.ff]=i.ss;
            par[i.ff]=v;
            dfs(i.ff);
        }
    }
    cup[par[v]]+=cup[v];
    if(cup[v]>1) merge(v,par[v]);
}
void dfs2(int v,int u){
    dept[v]=dept[u]+1;
    par[v]=u;
    vis[v]=1;
    for(auto& i:g[v]){
        if(i.ff==u) continue;
        cpar[i.ff]=i.ss;
        dfs2(i.ff,v);
    }
}
void solve(){
    pii pi,pj;
    int n,m,o,p,q;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        c[i]='B';
        cin>>p>>q;
        edge[i]={p,q};
        a[p].append({q,i});
        a[q].append({p,i});
    }
    for(int i=1;i<=n;i++){
        if(dept[i]) continue;
        dept[i]=1;
        dfs(i);
    }
    for(int i=2;i<=n;i++){
        if(same(i,par[i])) continue;
        p=root(i);
        q=root(par[i]);
        g[p].append({q,cpar[i]});
        g[q].append({p,cpar[i]});
    }
    for(int i=1;i<=n;i++){
        if(!vis[root(i)])
            dfs2(root(i),0);
    }
    cin>>o;
    while(o--){
        cin>>p>>q;
        p=root(p);
        q=root(q);
        while(p!=q){
            if(dept[p]>dept[q]){
                pj={p,par[p]};
                pi=edge[cpar[p]];
                pi.ff=root(pi.ff);
                pi.ss=root(pi.ss);
                if(pj==pi)
                    c[cpar[p]]='R';
                else c[cpar[p]]='L';
                p=par[p];
            }
            else{
                pj={q,par[q]};
                pi=edge[cpar[q]];
                pi.ff=root(pi.ff);
                pi.ss=root(pi.ss);
                if(pj==pi)
                    c[cpar[q]]='L';
                else c[cpar[q]]='R';
                q=par[q];
            }
        }
    }
    for(int i=0;i<m;i++)
        cout<<c[i];
}
int terminator(){
    L0TA;
    solve();
    return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 0 / 40