oj.uz

Submission #914192

# Submission time Handle Problem Language Result Execution time Memory
914192 2024-01-21T10:40:33 Z sleepntsheep One-Way Streets (CEOI17_oneway) C++17
0 / 100
 10 ms 34396 KB 
#include <stack>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>
#include <complex>

using namespace std;
#define ALL(x) begin(x), end(x)
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
#define N 200005

int n, m, p;
basic_string<pair<int, int>> g[N];
int a[N][2];

int tin[N], low[N], timer; char ans[N];
int grp[N], twoedgecc;

stack<int> sd;

void tarjan(int u, int p)
{
    tin[u] = low[u] = ++timer;
    sd.push(u);

    int parallel = 0;
    for (auto [v, eid] : g[u])
    {
        if (v == p && !parallel)
        {
            parallel = 1;
            continue;
        }
        if (!tin[v])
        {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
        }
        else low[u] = min(low[u], tin[v]);
    }

    if (tin[u] == low[u])
    {
        while (sd.top() != u)
        {
            grp[sd.top()] = twoedgecc;
            sd.pop();
        }
        grp[sd.top()] = twoedgecc++;
        sd.pop();
    }
}

basic_string<pair<int, int>> G[N];

set<pair<int, int>> to[N], from[N];
set<int> towait, fromwait;
int vis[N];

void dfs(int u, int p)
{
    vis[u] = 1;
    for (auto [v, eid] : G[u])
    {
        if (!vis[v])
        {
            dfs(v, u);
            assert(towait.empty() or fromwait.empty());

            if (towait.size())
            {
                if (eid > 0) ans[eid] = 'R';
                else ans[-eid] = 'L';
            }
            if (fromwait.size())
            {
                if (eid > 0) ans[eid] = 'L';
                else ans[-eid] = 'R';
            }
        }
        else if (v != p)
            assert(0);
    }

    for (auto [v, qid] : to[u])
    {
        if (fromwait.count(qid)) fromwait.erase(qid);
        else towait.insert(qid);
    }
    for (auto [v, qid] : from[u])
    {
        if (towait.count(qid)) towait.erase(qid);
        else fromwait.insert(qid);
    }
}

int main()
{
    ShinLena;
    cin >> n >> m;
    for (int u, v, i = 1; i <= m; ++i)
        cin >> u >> v, g[u].push_back({v, i}), g[v].push_back({u, -i}), ans[i] = 'B';

    for (int i = 1; i <= n; ++i) if (!tin[i]) tarjan(i, -1);

    cin >> p;
    for (int i = 0; i < p; ++i)
    {
        cin >> a[i][0] >> a[i][1];
        if (grp[a[i][0]] == grp[a[i][1]]) ;
        else
        {
            to[grp[a[i][1]]].insert({grp[a[i][0]], i});
            from[grp[a[i][0]]].insert({grp[a[i][1]], i});
        }
    }

    for (int i = 1; i <= n; ++i)
        for (auto [v, eid] : g[i])
            if (eid > 0 and grp[i] != grp[v])
                G[grp[i]].push_back({grp[v], eid}), G[grp[v]].push_back({grp[i], -eid});

    for (int i = 0; i < twoedgecc; ++i)
        sort(ALL(G[i])), G[i].resize(unique(ALL(G[i])) - G[i].begin());

    dfs(0, -1);

    cout << (ans+1);

    return 0;
}

Subtask #1
0 / 30.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 40.0

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