Submission #1295063

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295063		k12_khoi	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	81 ms	19396 KiB

oneway

#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];
}

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