oj.uz

Submission #701127

# Submission time Handle Problem Language Result Execution time Memory
701127 2023-02-20T06:57:56 Z Darren0724 One-Way Streets (CEOI17_oneway) C++17
0 / 100
 1 ms 468 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
int n,m;
vector<int> a,b;
vector<int> low,in;
vector<vector<int>> adj;
vector<int> ab,br;
vector<int> num;
vector<int> bcc;
vector<int> st;
vector<int> dx;
vector<int> dis;
int timet=1,bcc_cnt=0;
void dfs1(int k,int pa){
    in[k]=low[k]=timet++;
    st.push_back(k);
    for(int i:adj[k]){
        int j=ab[i]^k;
        if(pa==j){
            continue;
        }
        if(low[j]){
            low[k]=min(low[k],in[j]);
        }
        else{
            dfs1(j,k);
            low[k]=min(low[k],low[j]);
            if(low[j]>in[k]){
                br[i]=1;
            }
        }
    }
    if(low[k]==in[k]){
        while(st.back()!=k){
            bcc[st.back()]=bcc_cnt;
            st.pop_back();
        }
        st.pop_back();
        bcc[k]=bcc_cnt;
        bcc_cnt++;
    }
}
void dfs2(int k,int pa){
    for(int j:adj[k]){
        if(j==pa){
            continue;
        }
        dis[j]=dis[k]+1;
        dfs2(j,k);
        dx[k]+=dx[j];
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    adj.resize(n);
    in.resize(n);
    low.resize(n);
    ab.resize(m);
    br.resize(m);
    a.resize(m);
    b.resize(m);
    bcc.resize(n);
    for(int i=0;i<m;i++){
        cin>>a[i]>>b[i];a[i]--;b[i]--;
        adj[a[i]].push_back(i);
        adj[b[i]].push_back(i);
        ab[i]=a[i]^b[i];
    }
    for(int i=0;i<n;i++){
        if(in[i]==0)dfs1(i,-1);
    }
    for(int i=0;i<m;i++){
        a[i]=bcc[a[i]];
        b[i]=bcc[b[i]];
    }
    adj.clear();
    adj.resize(bcc_cnt+1);
    dis.resize(bcc_cnt+1);
    dx.resize(bcc_cnt+1);
    for(int i=0;i<m;i++){
        if(br[i]==0){
            continue;
        }
        adj[a[i]].push_back(b[i]);
        adj[b[i]].push_back(a[i]);
    }
    for(int i=0;i<bcc_cnt;i++){
        sort(all(adj[i]));
        adj[i].resize(unique(all(adj[i]))-adj[i].begin());
    }
    int q;cin>>q;
    for(int i=0;i<q;i++){
        int c,d;cin>>c>>d;c--;d--;
        c=bcc[c],d=bcc[d];
        dx[c]++;
        dx[d]--;
    }
    for(int i=0;i<bcc_cnt;i++){
        if(dis[i]==0){
            dis[i]=1;
            dfs2(i,-1);
        }
    }
    for(int i=0;i<m;i++){
        if(!br[i]){
            cout<<'B';
        }
        else{
            assert(abs(dis[a[i]]-dis[b[i]])==1);
            if(dis[a[i]]>dis[b[i]]){
                if(dx[a[i]]==0){
                    cout<<'B';
                }
                else if(dx[a[i]]>0){
                    cout<<'R';
                }
                else{
                    cout<<'L';
                }
            }
            else{
                if(dx[b[i]]==0){
                    cout<<'B';
                }
                else if(dx[b[i]]>0){
                    cout<<'L';
                }
                else{
                    cout<<'R';
                }
            }
        }
    }

    return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 324 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Incorrect 1 ms 328 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 324 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Incorrect 1 ms 328 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 324 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Incorrect 1 ms 328 KB Output isn't correct
10 Halted 0 ms 0 KB -