Submission #1353496

#TimeUsernameProblemLanguageResultExecution timeMemory
1353496goulthenOne-Way Streets (CEOI17_oneway)C++20
0 / 100
4 ms348 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define per(i,a,b) for (int i = a; i >= b; i--)
#define pii pair<int,int>
#define fi first
#define se second
#define endl '\n'
#define pb push_back
#define all(v) (v).begin(), (v).end()

const int MAXN = 5e5+10;
const int INF = 1e18+10;
const int MOD = 1e9+7;
vector<pii> g[MAXN];
vector<int> t[MAXN];
int tin[MAXN],mk[MAXN], eid[MAXN], dp[MAXN],dir[MAXN],down[MAXN],tempo;
string ans;

void dfs(int u, int p = -1) {
    if (mk[u]) {
        if(tin[u] < tin[p]) {
            dp[p]++;
            dp[u]--;
        }
        return;
    }
    if(p!=-1) t[p].pb(u);
    mk[u] = 1;
    tin[u] = ++tempo;
    for(auto &[v,i] : g[u]) {
        if(v==p) continue;
        dfs(v,u);
        if(i>0) down[u] = 1;
        else down[u] = 0;
        eid[v] = abs(i);
    }
}

void calc(int u) {
    for(int &v : t[u]) {
        calc(v);
        dp[u] += dp[v];
        dir[u]+=dir[v];
    }

    if(u!=1 && dp[u]==0 && dir[u] != 0) {
        if((down[u] && dir[u]>0) || (!down[u] && dir[u]<0)) ans[eid[u]-1] = 'L';
        else ans[eid[u]-1] = 'R'; 
    }
}

void solve() {
    int n,m; cin >> n >> m;
    rep(i,1,m) {
        int u,v; cin >> u >> v;
        g[u].pb({v,i});
        g[v].pb({u,-i});
    }
    int p; cin >> p;
    rep(i,1,p) {
        int u,v; cin >> u >> v;
        dir[u]++;
        dir[v]--;
    }
    rep(i,1,m) ans += 'B';
    dfs(1);

    calc(1);
    cout << ans << endl;
}

int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(nullptr);
	int tt = 1;
    //cin >> tt;
    
    while(tt--) solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...