oj.uz

Submission #692539

# Submission time Handle Problem Language Result Execution time Memory
692539 2023-02-01T19:46:16 Z finn__ One-Way Streets (CEOI17_oneway) C++17
0 / 100
 1 ms 468 KB 
#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;

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.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -