제출 #1160732

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1160732		Nguyen22cpp	One-Way Streets (CEOI17_oneway)	C++20	0 / 100	2 ms	5184 KiB

oneway

#include <bits/stdc++.h>
using namespace std;

#define TASK "test"
#define int long long
#define ii pair <int, int>
#define fi first
#define sc second

#define rep(i,s,e) for (int i = (s), _e = (e); i <= _e; i++)
#define reo(i,s,e) for (int i = (s), _e = (e); i >= _e; i--)

const int maxn = (int)1e5 + 5;
const int inf = (int)1e9;
const int mod = (int)1e9 + 7;

int n, m, p;
vector <int> adj[maxn];
ii edge[maxn];
unordered_map <int, int> lab;
bool check[maxn];

int timer, low[maxn], num[maxn];

void tarjan (int u = 1, int p = 0)
{
    low[u] = num[u] = ++timer;
    for (auto v : adj[u])
    {
        if (v == p) continue;
        if (num[v]) low[u] = min(low[u], num[v]);
        else
        {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] == num[v]) check[lab[u * n + v]] = true;
        }
    }
}

int par[maxn], sz[maxn];

int find (int u)
{
    return par[u] == u ? u : par[u] = find(par[u]);
}

void uniset (int u, int v)
{
    u = find(u), v = find(v);
    if (u == v) return ;

    if (sz[u] < sz[v]) swap(u, v);
    par[v] = u, sz[u] += sz[v];
}

struct DATA
{
    int u, e, is;
} up[maxn];
vector <DATA> new_adj[maxn];
int depth[maxn], ans[maxn];

void dfs (int u = 1, int p = 0)
{
    for (auto [v, e, is] : new_adj[u])
    {
        if (v == p) continue;
        depth[v] = depth[u] + 1;
        up[v] = {u, e, is ^ 1};
        dfs(v, u);
    }
}

signed main ()
{
    cin.tie(0)->sync_with_stdio(false);

    cin >> n >> m;
    rep (i, 1, m)
    {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        edge[i] = {u, v};
        lab[u * n + v] = lab[v * n + u] = i;
    }

    tarjan();

    rep (u, 1, n)
    {
        par[u] = u;
        sz[u] = 1;
    }

    rep (i, 1, m) if (!check[i])
    {
        int u, v; tie(u, v) = edge[i];
        uniset(u, v);
    }

    rep (i, 1, m) if (check[i])
    {
        int u, v; tie(u, v) = edge[i];
        u = find(u), v = find(v);
        new_adj[u].push_back({v, i, 1});
        new_adj[v].push_back({u, i, 0});
    }

    dfs();

    rep (i, 1, m) ans[i] = -1;

    cin >> p;
    while (p--)
    {
        int u, v; cin >> u >> v;
        u = find(u), v = find(v);
        if (u == v) continue;

        while (depth[u] > depth[v])
        {
            ans[up[u].e] = up[u].is;
            u = up[u].u;
        }

        while (depth[u] < depth[v])
        {
            ans[up[v].e] = up[v].is ^ 1;
            v = up[v].u;
        }

        while (u != v)
        {
            ans[up[u].e] = up[u].is;
            u = up[u].u;
            ans[up[v].e] = up[v].is ^ 1;
            v = up[v].u;
        }
    }

    rep (i, 1, m)
    {
        if (ans[i] == -1) cout << 'B';
        else cout << (ans[i] == 1 ? 'R' : 'L');
    }

    return 0;
}

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