oj.uz

답안 #838112

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
838112 2023-08-26T08:58:47 Z yeediot One-Way Streets (CEOI17_oneway) C++17
0 / 100
 6 ms 8916 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
const int mxn=1e5+5;
vector<int>adj[mxn];
unordered_set<int>nw[mxn];
int val[mxn];
int d[mxn];
struct edge{
    int v,u;
};
vector<edge>e;
bitset<mxn>vis;
int lv[mxn],low[mxn];
int timer=0;
stack<int>st;
vvi bcc;
vector<int>group(mxn);
void tarjan(int v,int pa=-1){
    lv[v]=low[v]=++timer;
    st.push(v);
    for(auto u:adj[v]){
        if(u==pa){
            pa=-1;
            continue;
        }
        if(lv[u]){
            chmin(low[v],lv[u]);
        }
        else{
            tarjan(u,v);
            chmin(low[v],low[u]);
        }
    }
    if(lv[v]==low[v]){
        bcc.pb({});
        while(st.top()!=v){
            bcc.back().pb(st.top());
            group[st.top()]=sz(bcc)-1;
            st.pop();
        }
        bcc.back().pb(st.top());
        group[st.top()]=sz(bcc)-1;
        st.pop();
    }
}
void dfs2(int v,int pa=-1){
    for(auto u:nw[v]){
        if(u==pa)continue;
        d[u]=d[v]+1;
        dfs2(u,v);
        val[v]+=val[u];
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        e.pb({a,b});
        adj[a].pb(b);
        adj[b].pb(a);
    }
    for(int i=1;i<=n;i++){
        if(!lv[i])tarjan(i);
    }
    for(int i=1;i<=m;i++){
        int a=e[i].v;
        int b=e[i].u;
        int x=group[a];
        int y=group[b];
        if(x!=y){
            nw[x].insert(y);
            nw[y].insert(x);
        }
    }
    int q;
    cin>>q;
    while(q--){
        int a,b;
        cin>>a>>b;
        val[group[a]]++;
        val[group[b]]--;
    }
    for(int i=0;i<sz(bcc);i++){
        if(!d[i])dfs2(i);
    }
    for(int i=0;i<m;i++){
        int x=group[e[i].v];
        int y=group[e[i].u];
        if(x==y){
            cout<<"B";
        }
        else{
            if(d[x]>d[y]){
                if(val[x]==0)cout<<"B";
                else if(val[x]>0)cout<<"R";
                else cout<<"L";
            }
            else{
                if(val[y]==0)cout<<"B";
                else if(val[y]<0)cout<<"R";
                else cout<<"L";
            }
        }
    }
}
 /*
 input:
 
 */

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8916 KB Output is correct
2 Incorrect 4 ms 8916 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8916 KB Output is correct
2 Incorrect 4 ms 8916 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8916 KB Output is correct
2 Incorrect 4 ms 8916 KB Output isn't correct
3 Halted 0 ms 0 KB -