Submission #1295063

#TimeUsernameProblemLanguageResultExecution timeMemory
1295063k12_khoiOne-Way Streets (CEOI17_oneway)C++17
100 / 100
81 ms19396 KiB
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define X first
#define Y second

const int N=1e5+5;

int n,m,request,x,y,timesdfs,tplt;
int save_x[N],save_y[N],low[N],num[N],scc[N],dp[N];
char ans[N];
bool visited[N];
vector <pii> adj[N],g[N];
stack <int> trace;

void dfs(int u,int root)
{
    num[u]=low[u]=++timesdfs;
    trace.push(u);

    for (pii v:adj[u])
    if (!scc[v.X])
    {
        if (v.Y!=root)
        {
            if (num[v.X]) low[u]=min(low[u],num[v.X]);
            else
            {
                dfs(v.X,v.Y);
                low[u]=min(low[u],low[v.X]);
            }
        }
    }

    if (num[u]==low[u])
    {
        tplt++;
        int k=-1;
        while (u!=k)
        {
            k=trace.top();
            trace.pop();
            scc[k]=tplt;
        }
    }
}

void final_dfs(int u)
{
    visited[u]=true;

    for (pii v:g[u])
    if (!visited[v.X])
    {
        final_dfs(v.X);

        if (dp[v.X]<0)
        {
            if (v.Y>0) ans[v.Y]='L';
            else ans[-v.Y]='R';
        }
        if (dp[v.X]>0)
        {
            if (v.Y>0) ans[v.Y]='R';
            else ans[-v.Y]='L';
        }

        dp[u]+=dp[v.X];
    }
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m;
    for (int i=1;i<=m;i++)
    {
        cin >> x >> y;
        adj[x].push_back(make_pair(y,i));
        adj[y].push_back(make_pair(x,i));

        save_x[i]=x;
        save_y[i]=y;
    }

    timesdfs=0;
    for (int i=1;i<=n;i++)
    if (!num[i]) dfs(i,-1);

    for (int i=1;i<=m;i++)
    {
        x=scc[save_x[i]];
        y=scc[save_y[i]];

        if (x!=y)
        {
            g[x].push_back(make_pair(y,i));
            g[y].push_back(make_pair(x,-i));
        }

        ans[i]='B';
    }


    for (int i=1;i<=tplt;i++)
    dp[i]=0;

    cin >> request;
    while (request--)
    {
        cin >> x >> y;
        x=scc[x];
        y=scc[y];

        if (x!=y)
        {
            dp[x]--;
            dp[y]++;
        }
    }

    for (int i=1;i<=tplt;i++)
    if (!visited[i]) final_dfs(i);

    for (int i=1;i<=m;i++)
    cout << ans[i];
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...