Submission #1335588

#TimeUsernameProblemLanguageResultExecution timeMemory
1335588algoproclubOne-Way Streets (CEOI17_oneway)C++20
0 / 100
1 ms344 KiB
// UUID: d5692679-dfc1-4bd7-84ce-11dadde4d66f
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define pii pair<int,int>
#define pb push_back
#define srt(x) x.begin(),x.end()

vector<vector<pii>> g;
vector<pii> e;
vector<int> tin, low, p;
vector<int> ans;
vector<int> cnt;
int tim = 0;

void dfs(int v)
{
    tin[v] = low[v] = ++tim;
    for(auto [u, id] : g[v])
    {
        if(u == p[v]) continue;
        if(!tin[u])
        {
            p[u] = v;
            dfs(u);

            low[v] = min(low[v], low[u]);

            cnt[v] += cnt[u];

            if(low[u] > tin[v])
            {
                if(cnt[u] > 0) ans[id] = 1;
                else if(cnt[u] < 0) ans[id] = 2;
                else ans[id] = 3;
            }
            else ans[id] = 3;
        }
        else
        {
            low[v] = min(low[v], tin[u]);
            ans[id] = 3;
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n, m; cin >> n >> m;
    g.resize(n); tin.resize(n); low.resize(n); p.resize(n,-1); ans.resize(m); e.resize(m); cnt.resize(n);
    for(int i = 0; i < m; i++)
    {
        int a, b; cin >> a >> b; --a;--b;
        g[a].pb({b, i});
        g[b].pb({a, i});
        e[i] = {a, b};
    }
    int q; cin >> q;
    while(q--)
    {
        int a, b; cin >> a >> b; --a;--b;
        cnt[a]++;
        cnt[b]--;
    }
    dfs(0);
    for(int i = 0; i < m; i++)
    {
        if(ans[i] == 3) cout << 'B';
        else if(ans[i] == 2)
        {
            if(e[i].F == p[e[i].S]) cout << 'R';
            else cout << 'L';
        }
        else
        {
            if(e[i].F == p[e[i].S]) cout << 'L';
            else cout << 'R';
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...