oj.uz

Submission #838131

# Submission time Handle Problem Language Result Execution time Memory
838131 2023-08-26T09:09:04 Z yeediot One-Way Streets (CEOI17_oneway) C++17
100 / 100
 70 ms 23324 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];
vector<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;
int bccnt=0;
vector<int>group(mxn);
vector<bool>bridge(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]){
            tarjan(u,v);
            chmin(low[v],low[u]);
        }
        else{
            chmin(low[v],lv[u]);
        }
    }
    if(lv[v]==low[v]){
        while(st.top()!=v){
            group[st.top()]=bccnt;
            st.pop();
        }
        group[st.top()]=bccnt;
        st.pop();
        bccnt++;
    }
}
void dfs2(int v,int pa=0){
    d[v]=d[pa]+1;
    vis[v]=1;
    for(auto u:nw[v]){
        if(vis[u])continue;
        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=0;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(!vis[i])tarjan(i,i);
    }
    for(int i=0;i<m;i++){
        int a=e[i].v;
        int b=e[i].u;
        if(group[a]!=group[b]){
            int x=group[a];
            int y=group[b];
            nw[x].pb(y);
            nw[y].pb(x);
        }
    }
    vector<char>ans(m+1,'B');
    int q;
    cin>>q;
    while(q--){
        int a,b;
        cin>>a>>b;
        val[group[a]]++;
        val[group[b]]--;
    }
    vis.reset();
    for(int i=0;i<bccnt;i++){
        if(!vis[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";
            }
        }
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5844 KB Output is correct
2 Correct 2 ms 5844 KB Output is correct
3 Correct 2 ms 5844 KB Output is correct
4 Correct 3 ms 5972 KB Output is correct
5 Correct 3 ms 5972 KB Output is correct
6 Correct 2 ms 5844 KB Output is correct
7 Correct 3 ms 5972 KB Output is correct
8 Correct 3 ms 5972 KB Output is correct
9 Correct 3 ms 5816 KB Output is correct
10 Correct 3 ms 5844 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5844 KB Output is correct
2 Correct 2 ms 5844 KB Output is correct
3 Correct 2 ms 5844 KB Output is correct
4 Correct 3 ms 5972 KB Output is correct
5 Correct 3 ms 5972 KB Output is correct
6 Correct 2 ms 5844 KB Output is correct
7 Correct 3 ms 5972 KB Output is correct
8 Correct 3 ms 5972 KB Output is correct
9 Correct 3 ms 5816 KB Output is correct
10 Correct 3 ms 5844 KB Output is correct
11 Correct 28 ms 11956 KB Output is correct
12 Correct 31 ms 13016 KB Output is correct
13 Correct 34 ms 14348 KB Output is correct
14 Correct 44 ms 16200 KB Output is correct
15 Correct 46 ms 16852 KB Output is correct
16 Correct 64 ms 18964 KB Output is correct
17 Correct 47 ms 20276 KB Output is correct
18 Correct 52 ms 19012 KB Output is correct
19 Correct 48 ms 21440 KB Output is correct
20 Correct 33 ms 12860 KB Output is correct
21 Correct 30 ms 12612 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5844 KB Output is correct
2 Correct 2 ms 5844 KB Output is correct
3 Correct 2 ms 5844 KB Output is correct
4 Correct 3 ms 5972 KB Output is correct
5 Correct 3 ms 5972 KB Output is correct
6 Correct 2 ms 5844 KB Output is correct
7 Correct 3 ms 5972 KB Output is correct
8 Correct 3 ms 5972 KB Output is correct
9 Correct 3 ms 5816 KB Output is correct
10 Correct 3 ms 5844 KB Output is correct
11 Correct 28 ms 11956 KB Output is correct
12 Correct 31 ms 13016 KB Output is correct
13 Correct 34 ms 14348 KB Output is correct
14 Correct 44 ms 16200 KB Output is correct
15 Correct 46 ms 16852 KB Output is correct
16 Correct 64 ms 18964 KB Output is correct
17 Correct 47 ms 20276 KB Output is correct
18 Correct 52 ms 19012 KB Output is correct
19 Correct 48 ms 21440 KB Output is correct
20 Correct 33 ms 12860 KB Output is correct
21 Correct 30 ms 12612 KB Output is correct
22 Correct 64 ms 20248 KB Output is correct
23 Correct 70 ms 18724 KB Output is correct
24 Correct 65 ms 18956 KB Output is correct
25 Correct 63 ms 23324 KB Output is correct
26 Correct 62 ms 19996 KB Output is correct
27 Correct 64 ms 18800 KB Output is correct
28 Correct 24 ms 9680 KB Output is correct
29 Correct 43 ms 12352 KB Output is correct
30 Correct 42 ms 12500 KB Output is correct
31 Correct 44 ms 12832 KB Output is correct
32 Correct 51 ms 16228 KB Output is correct