Submission #823713

#	Time	Username	Problem	Language	Result	Execution time	Memory
823713		12345678	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	54 ms	12552 KiB

oneway

#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5;
int n, m, p, ds[nx], l[nx], dp[nx], u, v, t;
char ans[2*nx];
vector<vector<tuple<int, int, bool>>> d(nx);

void tarj(int u, int pidx)
{
    ds[u]=l[u]=++t;
    for (auto [idx, v, dr]:d[u])
    {
        if (idx==pidx) continue;
        if (!ds[v])
        {
            tarj(v, idx);
            if (ds[u]>=l[v]||dp[v]==0) ans[idx]='B';
            else 
            {
                if (dp[v]>0) ans[idx]=(dr==1)?'L':'R';
                else ans[idx]=(dr==1)?'R':'L';
            }
            dp[u]+=dp[v];
            l[u]=min(l[v], l[u]);
        }
        else l[u]=min(l[u], l[v]), ans[idx]='B';
        //printf("%d %d %d %c\n", u, v, idx, ans[idx]);
    }
    //printf("%d %d %d\n", u, ds[u], l[u]);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=0; i<m; i++) cin>>u>>v, d[u].push_back({i, v, 1}), d[v].push_back({i, u, 0});
    cin>>p;
    for (int i=0; i<p; i++) cin>>u>>v, dp[u]++, dp[v]--;
    for (int i=1; i<=n; i++) if (!ds[i]) tarj(i, -1);
    for (int i=0; i<m; i++) cout<<ans[i];
}

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