Submission #1264277

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264277		goppamach	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	209 ms	27668 KiB

oneway

#include <bits/stdc++.h>

using namespace std;

#define el "\n"
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define FOR(i, l, r) for (int i = l; i <= (r); i++)
#define FOD(i, l, r) for (int i = l; i >= (r); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define sqr(x) (x) * (x)
#define fast_io ios_base::sync_with_stdio(false); cin.tie(nullptr);

using db = long double;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vll = vector<ll>;
using vpii = vector<pii>;
using vpll = vector<pll>;
using vvi = vector<vi>;
using vvll = vector<vll>;
using vbool = vector<bool>;
using vvbool = vector<vbool>;

template<class T> bool chmax(T &a, T const &b) { return (a < b ? (a = b, true) : false); }
template<class T> bool chmin(T &a, T const &b) { return (a > b ? (a = b, true) : false); }

// #define DEBUG
#ifdef DEBUG
#include "D:\cpp\debug.h"
#else
#define debug(...)
#define debug_arr(...)
#endif

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

constexpr int N = 1E5 + 5, EXP = 20;
constexpr int INF = 1E9 + 7;
constexpr ll INFLL = 1E18;
constexpr int MOD = 1E9 + 7; // 998244353
constexpr double EPS = 1E-10;

vi adj[N], adj_comp[N];
struct Edge {
    int u, v;
    Edge() = default;
    Edge(int u, int v): u(u), v(v) {}
    int other(int w) { return u ^ v ^ w; }
} edges[N];
int low[N], num[N], comp[N], up[N], down[N];
int lift[N][EXP + 1], depth[N];
bool bridge[N];
char res[N];
int counter = 0, cid = 0;
int n, m;

void tarjan(int u, int pid = 0) {
    low[u] = num[u] = ++counter;
    for (int id : adj[u]) {
        int v = edges[id].other(u);
        if (!num[v]) {
            tarjan(v, id);
            chmin(low[u], low[v]);
            if (low[v] > num[u]) {
                bridge[id] = true;
            }
        } else if (id != pid) {
            chmin(low[u], num[v]);
        }
    }
}

void dfs_comp(int u, int cid) {
    comp[u] = cid;
    for (int id : adj[u]) {
        int v = edges[id].other(u);
        if (!comp[v] && !bridge[id]) {
            dfs_comp(v, cid);
        }
    }
}

void dfs_lift(int u, int p = 0) {
    lift[u][0] = p;
    FOR(e, 1, EXP) {
        lift[u][e] = lift[lift[u][e - 1]][e - 1];
    }
    for (int v : adj_comp[u]) {
        if (v != p) {
            depth[v] = depth[u] + 1;
            dfs_lift(v, u);
        }
    }
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    FOD(e, EXP, 0) {
        if (depth[u] - (1 << e) >= depth[v]) {
            u = lift[u][e];
        }
    }
    if (u == v) return u;
    FOD(e, EXP, 0) {
        if (lift[u][e] != lift[v][e]) {
            u = lift[u][e];
            v = lift[v][e];
        }
    }
    return lift[u][0];
}

void dfs_acc(int u, int p = 0) {
    for (int v : adj_comp[u]) {
        if (v != p) {
            dfs_acc(v, u);
            up[u] += up[v];
            down[u] += down[v];
        }
    }
}

void solve() {
    cin >> n >> m;

    FOR(i, 1, m) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(i);
        adj[b].push_back(i);
        edges[i] = {a, b};
    }

    FOR(i, 1, n) {
        if (!num[i]) {
            tarjan(i);
        }
    }

    cid = 0;
    FOR(i, 1, n) {
        if (!comp[i]) {
            dfs_comp(i, ++cid);
        }
    }

    fill(res + 1, res + m + 1, 'B');
    FOR(i, 1, m) {
        if (bridge[i]) {
            res[i] = '?';
            auto e = edges[i];
            adj_comp[comp[e.u]].push_back(comp[e.v]);
            adj_comp[comp[e.v]].push_back(comp[e.u]);
        }
    }

    FOR(i, 1, cid) {
        if (!depth[i]) {
            dfs_lift(i);
        }
    }

    int p; cin >> p; while (p--) {
        int a, b;
        cin >> a >> b;
        a = comp[a]; b = comp[b];
        if (a == b) continue;
        int x = lca(a, b);
        up[a]++; up[x]--;
        down[b]++; down[x]--;
    }

    FOR(i, 1, cid) {
        if (!lift[i][0]) {
            dfs_acc(i);
        }
    }

    FOR(i, 1, m) {
        if (res[i] == '?') {
            auto e = edges[i];
            int u = comp[e.u], v = comp[e.v];
            bool reversed = false;
            if (depth[u] < depth[v]) {
                reversed = true;
                swap(u, v);
            }
            if (up[u] > 0) {
                res[i] = reversed ? 'L' : 'R';
            } else if (down[u] > 0) {
                res[i] = reversed ? 'R' : 'L';
            } else {
                res[i] = 'B'; // should be unreachable
            }
        }
        cout << res[i];
    }
    cout << el;
}

int main() {
    fast_io
    #define LOCAL
    #ifndef LOCAL
    #define PROBLEM ""
    freopen(PROBLEM ".INP", "r", stdin);
    freopen(PROBLEM ".OUT", "w", stdout);
    #endif

    int t = 1;
    // cin >> t;
    while (t--) solve();
}

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