제출 #692538

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
692538		finn__	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	1 ms	468 KiB

oneway

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

struct Edge
{
    unsigned v, i;
    bool as_given;
};

vector<vector<Edge>> g;
vector<int> r;
vector<unsigned> y, l;
vector<bool> visited;
string orientation;
char directions[2] = {'L', 'R'};

unsigned orient_edges(unsigned u, unsigned p = -1, unsigned i = 0)
{
    visited[u] = 1;
    y[u] = l[u] = i++;

    for (Edge const &e : g[u])
    {
        if (!visited[e.v])
        {
            i = orient_edges(e.v, u, i);
            r[u] += r[e.v];
            l[u] = min(l[u], l[e.v]);
        }

        if (e.v != p)
        {
            if (l[e.v] > y[u] && r[e.v])
                orientation[e.i] = ((r[e.v] > 0) ^ !e.as_given) ? 'L' : 'R';
            else
                orientation[e.i] = 'B';

            l[u] = min(l[u], y[e.v]);
        }
    }

    return i;
}

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

    size_t n, m;
    cin >> n >> m;

    g = vector<vector<Edge>>(n);
    r = vector<int>(n, 0);
    y = vector<unsigned>(n);
    l = vector<unsigned>(n);
    visited = vector<bool>(n, 0);
    orientation.resize(m);

    for (unsigned i = 0; i < m; i++)
    {
        unsigned u, v;
        cin >> u >> v;
        g[u - 1].push_back({v - 1, i, 1});
        g[v - 1].push_back({u - 1, i, 0});
    }

    size_t p;
    cin >> p;

    for (size_t i = 0; i < p; i++)
    {
        unsigned u, v;
        cin >> u >> v;
        r[u - 1]++;
        r[v - 1]--;
    }

    assert(orient_edges(0) == n);

    cout << orientation << '\n';
}

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