Submission #1259508

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259508		vuviet	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	98 ms	26084 KiB

oneway

/**
 *  __      __   __      __
 *  \ \    / /   \ \    / (_)     _____
 *   \ \  / /_   _\ \  / / _  ___|_   _|
 *    \ \/ /| | | |\ \/ / | |/ _ \ | |
 *     \  / | |_| | \  /  | |  __/ | |
 *      \/   \__,_|  \/   |_|\____||_|
 *
 *     Author:    VuViet
 *     Ready, set, code! #CPMode
 **/

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define ____VuViet__ signed main

const int N = 1e5 + 5;
int cnt = 0, id = 0, n, m, k;

int num[N], low[N], comp[N], sum[N];
int res[N], inStk[N], vis[N];

vector<pair<int, int>> g1[N], g2[N];
stack<int> stk;

void Tarjan(int u, int p)
{
    num[u] = low[u] = ++id;
    inStk[u] = 1;
    stk.push(u);
    for (auto [v, id] : g1[u])
    {
        if (id == -p) continue;
        if (!num[v])
        {
            Tarjan(v, id);
            low[u] = min(low[u], low[v]);
        } else if (inStk[v]) {
            low[u] = min(low[u], num[v]);
        }
    }
    if (low[u] >= num[u])
    {
        ++cnt;
        int v;
        do
        {
            v = stk.top();
            stk.pop();
            inStk[v] = 0;
            comp[v] = cnt;
        } while (v != u);
    }
}

void ReadData()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        g1[u].push_back({v, i});
        g1[v].push_back({u, -i});
    }
}


void DFS(int u, int edgeId, int dir)
{
    vis[u] = 1;
    for (auto [v, id] : g2[u])
    {
        if (vis[v]) continue;
        int ndir = (id > 0) ? 1 : -1;
        DFS(v, abs(id), ndir);
        sum[u] += sum[v];
    }
    if (sum[u] != 0 && edgeId != 0) {
        res[edgeId] = (sum[u] * dir > 0) ? 1 : 2;
    }
}

char GetChar(int x)
{
    if (x == 0) return 'B';
    if (x == 1) return 'L';
    return 'R';
}

void Solve()
{
    for (int i = 1; i <= n; i++)
        if (!num[i])
            Tarjan(i, i);
    for (int u = 1; u <= n; u++)
        for (auto [v, id] : g1[u])
            if (comp[u] != comp[v])
                g2[comp[u]].push_back({comp[v], id});
    cin >> k;
    while (k--)
    {
        int u, v;
        cin >> u >> v;
        ++sum[comp[u]], --sum[comp[v]];
    }
    for (int i = 1; i <= cnt; i++)
        if (!vis[i])
            DFS(i, 0, 0);
    for (int i = 1; i <= m; i++)
        cout << GetChar(res[i]);
}

____VuViet__()
{
    ReadData();
    Solve();
    return 0;
}

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