Submission #914172

#	Time	Username	Problem	Language	Result	Execution time	Memory
914172		sleepntsheep	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	10 ms	36444 KiB

oneway

#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 pe)
{
    tin[u] = low[u] = ++timer;
    sd.push(u);

    for (auto [v, eid] : g[u])
    {
        eid = abs(eid);
        if (eid == pe) continue;
        if (!tin[v])
            tarjan(v, eid);
        low[u] = min(low[u], low[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 (abs(eid) == p) continue;
        if (!vis[v])
        {
            dfs(v, abs(eid));
            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';

    tarjan(1, -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, 0);

    cout << (ans+1);

    return 0;
}

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