Submission #1005220

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005220		milisav	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	1 ms	4184 KiB

oneway

#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];
        }
        else {
            if(v!=p) low[u]=min(low[u],disc[v]);
        }
    }
    if(low[u]==disc[u] && p!=-1) {
        if(l[u]>r[u]) s[pi]='R';
        if(l[u]<r[u]) s[pi]='L';
    }
}
int main() {
    cin.tie(0); ios_base::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=0;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]++;
    }
    dfs(1,-1,-1);
    cout<<s<<endl;
    return 0;
}

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