제출 #337989

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
337989		rrrr10000	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	224 ms	28264 KiB

oneway

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef vector<ll> vi;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<PP> vpp;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(v) v.begin(),v.end()
#define dupli(v) {sort(all(v));v.erase(unique(all(v)),v.end());}
#define rsort(a) {sort(all(a));reverse(all(a));}
#define pb emplace_back
#define fi first
#define se second
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
template<class T>bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T>bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T>void out(T a){cout<<a<<endl;}
template<class T>void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<endl;}
template<class T>void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
template<class T>void outvp(T v){for(auto a:v)cout<<'('<<a.fi<<','<<a.se<<')';cout<<endl;}
template<class T>void outvv(T v){for(auto x:v)outv(x);}
template<class T>void outvvp(T v){for(auto x:v)outvp(x);}
const ll inf=1001001001001001001;
class UF{
    vi sz,par;
public:
    UF(ll n){
        sz=vi(n,1);rep(i,n)par.pb(i);
    }
    ll root(int i){
        if(par[i]==i)return i;
        return root(par[i]);
    }
    void merge(int a,int b){
        a=root(a);b=root(b);
        if(a==b)return;
        if(sz[a]>sz[b])swap(a,b);
        par[a]=b;
        sz[b]+=sz[a];
    }
};
int main(){
    ll n,m;cin>>n>>m;
    vvp g(n);
    vb rev(m,false);
    rep(i,m){
        ll a,b;cin>>a>>b;a--;b--;
        g[a].pb(b,i);g[b].pb(a,-i-1);
    }
    vi ans(m),dep(n,-1),lk(n,inf);
    vp par(n,P(-1,-1));
    UF uf(n);
    function<void(ll,ll,ll)> dfs=[&](ll i,ll p,ll e){
        for(P x:g[i])if(x.se!=e&&-1-x.se!=e){
            if(dep[x.fi]==-1){
                if(x.se<0){
                    x.se*=-1;x.se--;rev[x.se]=true;
                }
                dep[x.fi]=dep[i]+1;
                dfs(x.fi,i,x.se);
                chmin(lk[i],lk[x.fi]);
            }
            else{
                if(x.se<0){
                    x.se*=-1;x.se--;
                }
                else rev[x.se]=true;
                chmin(lk[i],dep[x.fi]);
            }
        }
        if(lk[i]<dep[i])uf.merge(i,p);
        else par[uf.root(i)]=P(p,e);
    };
    vi rt;
    rep(i,n)if(dep[i]==-1){
        rt.pb(i);
        dep[i]=0;
        dfs(i,-1,-1);
    }
    vvp tree(n);
    rep(i,n)if(par[i].fi!=-1)tree[uf.root(par[i].fi)].pb(i,par[i].se);
    vi cnt(n);
    ll q;cin>>q;
    rep(i,q){
        ll a,b;cin>>a>>b;a--;b--;
        cnt[uf.root(a)]++;cnt[uf.root(b)]--;
    }
    function<ll(ll,ll,ll)> add=[&](ll i,ll p,ll e){
        for(auto x:tree[i])if(x.fi!=p)cnt[i]+=add(x.fi,i,x.se);
        if(cnt[i]>0)ans[e]=1;
        if(cnt[i]<0)ans[e]=-1;
        return cnt[i];
    };
    for(ll x:rt)add(uf.root(x),-1,-1);
    rep(i,m)if(rev[i])ans[i]*=-1;
    rep(i,m){
        if(ans[i]==-1)cout<<'R';
        if(ans[i]==0)cout<<'B';
        if(ans[i]==1)cout<<'L';
    }cout<<endl;
}

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