제출 #42961

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
42961		krauch	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	133 ms	55920 KiB

oneway

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair < int, int > PII;

#define F first
#define S second
#define mkp make_pair
#define eb emplace_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define y1 kekek
#define left(v) v << 1
#define right(v) v << 1 | 1
#define forn(x, a, b) for (int x = a; x <= b; ++x)
#define for1(x, a, b) for (int x = a; x >= b; --x)

const ll ool = 1e18 + 9;
const int N = 2e5 + 6, oo = 1e9 + 9, base = 1e9 + 7;

int n, m, Q, cnt, timer, tin[N], d[N], col[N], val[N], dp[N], a[N], b[N];
char ans[N];
bool u[N], bridge[N];
vector < PII > g[N], g2[N];
vector < int > vec;

void dfs(int v, int par) {
    u[v] = 1;
    tin[v] = ++timer;
    d[v] = tin[v];
    for (auto it : g[v]) {
        int to = it.F;
        if (it.S == par) continue;
        if (u[to]) {
            d[v] = min(d[v], tin[to]);
        }
        else {
            int cur = sz(vec);
            dfs(to, it.S);
            d[v] = min(d[v], d[to]);
            if (d[to] > tin[v]) {
                bridge[it.S] = 1;
                ++cnt;
                while (sz(vec) != cur) {
                    col[vec.back()] = cnt;
                    vec.pop_back();
                }
            }
        }
    }
    vec.eb(v);
}

void calc(int v) {
    u[v] = 1;
    for (auto it : g2[v]) {
        int to = it.F;
        if (u[to]) continue;
        calc(to);
        dp[v] += dp[to];
        if (dp[to] < 0) ans[it.S] = (col[a[it.S]] == v ? 'R' : 'L');
        if (dp[to] == 0) ans[it.S] = 'B';
        if (dp[to] > 0) ans[it.S] = (col[a[it.S]] == v ? 'L' : 'R');
    }
}

int main() {
    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    #ifdef krauch
        freopen("input.txt", "r", stdin);
    #endif

    cin >> n >> m;
    forn(i, 1, m) {
        int x, y;
        cin >> x >> y;
        g[x].eb(y, i);
        g[y].eb(x, i);
        a[i] = x;
        b[i] = y;
    }

    cin >> Q;
    forn(i, 1, Q) {
        int x, y;
        cin >> x >> y;
        val[x]++;
        val[y]--;
    }

    forn(i, 1, n) {
        if (!u[i]) {
            dfs(i, 0);
            ++cnt;
            while (sz(vec)) {
                col[vec.back()] = cnt;
                vec.pop_back();
            }
        }
    }

    forn(i, 1, m) {
        if (!bridge[i]) {
            ans[i] = 'B';
            continue;
        }
        g2[col[a[i]]].eb(col[b[i]], i);
        g2[col[b[i]]].eb(col[a[i]], i);
    }

    forn(i, 1, n) {
        u[i] = 0;
        dp[col[i]] += val[i];
    }

    forn(i, 1, cnt) {
        if (!u[i]) calc(i);
    }

    forn(i, 1, m) cout << ans[i];
    cout << "\n";

    return 0;
}

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