Submission #692544

#	Time	Username	Problem	Language	Result	Execution time	Memory
692544		finn__	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	68 ms	14032 KiB

oneway

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

struct Edge
{
    unsigned v, i;
    bool as_given;

    Edge(unsigned v_, unsigned i_, bool as_given_)
    {
        v = v_, i = i_, as_given = as_given_;
    }
};

vector<vector<Edge>> g;
vector<int> r;
vector<unsigned> y, l;
vector<bool> visited;
string orientation;

unsigned orient_edges(unsigned u, Edge p = Edge(-1, -1, 0), 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, e, i);
            r[u] += r[e.v];
            l[u] = min(l[u], l[e.v]);
        }

        if (e.i != p.i)
        {
            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].emplace_back(v - 1, i, 1);
        g[v - 1].emplace_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]--;
    }

    for (unsigned i = 0; i < n; i++)
        if (!visited[i])
            orient_edges(i);

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

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