Submission #1027345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027345		ara_ara	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	67 ms	30036 KiB

oneway

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+5;
vector<pair<int,int>> adj[maxn],tree[maxn];
pair<int,int> edge[maxn];
int n,m,p;
char res[maxn];
int low[maxn],num[maxn],stt[maxn],del[maxn],cc,timedfs;
int a[maxn],b[maxn];
stack<int> st;
void dfs1(int u,int p){
    num[u]=low[u]=++timedfs;
    st.push(u);
    bool skip=false;
    for(auto i:adj[u]){
        int v=i.first;
        if(v==p && !skip){
            skip=true;
            continue;
        }
        if(!num[v]){
            dfs1(v,u);
            low[u]=min(low[u],low[v]);
        }
        else low[u]=min(low[u],num[v]);
    }
    if(low[u]==num[u]){
        cc++;
        int v;
        do{
            v=st.top();
            st.pop();
            stt[v]=cc;
            del[v]=true;
        }
        while(v!=u);
    }
}
int vis[maxn];
vector<int> dir[maxn]; 
void dfs2(int u,int idx){
    vis[u]=1;
    for(auto i:tree[u])if(!vis[i.first]){
        dfs2(i.first,i.second);
        a[u]+=a[i.first];
        b[u]+=b[i.first];
    }
    if(a[u]==b[u]) res[idx]='B';
    else if(a[u]>b[u]){
        if(stt[edge[idx].first]==u) res[idx]='R';
        else res[idx]='L';
    }
    else{
        if(stt[edge[idx].first]==u) res[idx]='L';
        else res[idx]='R';
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        edge[i]={u,v};
        adj[u].push_back({v,i});
        adj[v].push_back({u,i});
    }
    for(int i=1;i<=n;i++) if(!del[i]) dfs1(i,i);
    for(int u=1;u<=n;u++)
        for(auto i:adj[u])
            if(stt[u]!=stt[i.first]) tree[stt[u]].push_back({stt[i.first],i.second});
    cin>>p;
    for(int i=1;i<=p;i++){
        int u,v;
        cin>>u>>v;
        if(stt[u]==stt[v]) continue;
        a[stt[u]]++;
        b[stt[v]]++;
    }
    for(int i=1;i<=cc;i++) if(!vis[i]) dfs2(i,0);
    for(int i=1;i<=m;i++){
        if(!res[i]) cout<<'B';
        else cout<<res[i];
    }
}

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