Submission #938464

#	Time	Username	Problem	Language	Result	Execution time	Memory
938464		vjudge1	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	2 ms	2908 KiB

oneway

#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N=1e5+5;
vector <int> g[N];
int cl[N],cy[N],par[N];
vector <pair <int,int> > edg;
map <pair<int,int> ,int>  mp;
void dfs(int v,int p){
    if(cl[v]==2)return;
    if(cl[v]==1){
        mp[{v,p}]=1;
        int cur=p;
        cy[cur]=1;
        while(cur!=v){
            mp[{cur,par[cur]}]=1;
            cur=par[cur];
            cy[cur]=1;
        }
        return;
    }
    par[v]=p;
    cl[v]=1;
    for(auto to : g[v]){
        if(to!=par[v])dfs(to,v);
    }
    cl[v]=2;
}

signed main(){
    ios_base::sync_with_stdio();
    cin.tie(0);cout.tie(0);
    int n,m;
    cin>>n>>m;
    vector <int> a(m),b(m);
    for(int i=0;i<m;i++){
        cin>>a[i]>>b[i];
        g[a[i]].pb(b[i]);
        g[b[i]].pb(a[i]);
    }
    dfs(1,0);
    vector <char> ans(m,'B');
    int qu;cin>>qu;
    while(qu--){
        int s,t;
        cin>>s>>t;
        queue <int> q;
        q.push(s);
        vector <int> vis(n+1),pr(n+1);
        vis[s]=1;
        while(!q.empty()){
            int v=q.front();
            q.pop();
            for(auto to : g[v]){
                if(!vis[to]){
                    pr[to]=v;
                    vis[to]=1;
                    q.push(to);
                }
            }
        }
        while(t!=s){
            edg.pb({pr[t],t});
            t=pr[t];
        }
    }
    for(int i=0;i<m;i++){
        if(mp[{a[i],b[i]}] or mp[{b[i],a[i]}])continue;
        pair <int,int> p={a[i],b[i]};
        auto it=lower_bound(all(edg),p);
        if(it!=edg.end() && *it==p)ans[i]='R';
        p={b[i],a[i]};
        it=lower_bound(all(edg),p);
        if(it!=edg.end() && *it==p)ans[i]='L';
        
    }
    for(auto x : ans)cout<<x;
    
    
}
/*

*/

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