Submission #1005336

#TimeUsernameProblemLanguageResultExecution timeMemory
1005336milisavOne-Way Streets (CEOI17_oneway)C++14
100 / 100
36 ms12588 KiB
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
int n,m;
vector<pair<int,int> > a[maxn];
int disc[maxn];
int low[maxn];
int ct=1;
int l[maxn];
int r[maxn];
char s[maxn];
void dfs(int u,int p=-1,int pi=-1) {
    disc[u]=low[u]=ct++;
    for(auto vt:a[u]) {
        int v=vt.first;
        int i=vt.second;
        if(disc[v]==0) {
            dfs(v,u,i);
            low[u]=min(low[u],low[v]);
            l[u]+=l[v];
            r[u]+=r[v];
            if(low[v]>disc[u]) {
                if(i>0) {
                    if(l[v]>r[v]) s[i]='L';
                    if(l[v]<r[v]) s[i]='R';
                }
                else {
                    if(l[v]>r[v]) s[-i]='R';
                    if(l[v]<r[v]) s[-i]='L';
                }
            }
        }
        else {
            if(i+pi!=0) low[u]=min(low[u],disc[v]);
        }
    }
}
int main() {
    cin.tie(0); ios_base::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=m;i++) {
        int u,v;
        cin>>u>>v;
        a[u].push_back({v,i});
        a[v].push_back({u,-i});
        s[i]='B';
    }
    int p;
    cin>>p;
    for(int i=0;i<p;i++) {
        int u,v;
        cin>>u>>v;
        l[u]++;
        r[v]++;
    }
    for(int i=1;i<=n;i++) {
        if(disc[i]==0) dfs(i,-1,-1);
    }
    cout<<s+1<<endl;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...