oj.uz

Submission #692542

# Submission time Handle Problem Language Result Execution time Memory
692542 2023-02-01T20:09:22 Z finn__ One-Way Streets (CEOI17_oneway) C++17
0 / 100
 0 ms 212 KB 
#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]--;
    }

    orient_edges(0);

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

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -