Submission #1259804

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259804		vuviet	One-Way Streets (CEOI17_oneway)	C++20	0 / 100	4 ms	8256 KiB

oneway

/**
 *  __      __   __      __
 *  \ \    / /   \ \    / (_)     _____
 *   \ \  / /_   _\ \  / / _  ___|_   _|
 *    \ \/ /| | | |\ \/ / | |/ _ \ | |
 *     \  / | |_| | \  /  | |  __/ | |
 *      \/   \__,_|  \/   |_|\____||_|
 *
 *     Author:    ~Noah-kun~
 *     Created:   2025-08-17 22:18
**/

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define ____VuViet__ signed main

const int N = 1e5 + 5;
typedef pair<int, int> pii;

int cnt = 0, n, m, k, dd[N];
int comp[N], sum[N], res[N], vis[N];

vector<pii> g1[N], g2[N], dag[N];
deque<int> dq;

void AddEdge(int u, int v, int i)
{
    g1[u].push_back({v, i});
    g2[v].push_back({u, i});
}

void ReadData()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        AddEdge(u, v, i);
        AddEdge(v, u, -i);
    }
}

void Scan(int u, int p)
{
    dd[u] = 1;
    for (auto [v, id] : g1[u])
        if (!dd[v] && id != -p)
            Scan(v, id);
    dq.push_front(u);
}

void Enum(int u, int p)
{
    dd[u] = 1, comp[u] = cnt;
    for (auto [v, id] : g2[u])
        if (!dd[v] && id != -p)
            Enum(v, id);
}

void Kosaraju()
{
    for (int u = 1; u <= n; ++u)
        if (!dd[u])
            Scan(u, u);
    memset(dd, 0, sizeof(dd));
    for (int u : dq)
    {
        if (dd[u]) continue;
        ++cnt; Enum(u, u);
    }
}

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

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

void Solve()
{
    Kosaraju();
    for (int u = 1; u <= n; u++)
        for (auto [v, id] : g1[u])
            if (comp[u] != comp[v])
                dag[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: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40