Submission #1264485

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264485		biank	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	260 ms	58428 KiB

oneway

#include <bits/stdc++.h>
 
using namespace std;
 
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
#define foreach(it, c) for (auto it = begin(c); it != end(c); it++)
 
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)

#define pb push_back
#define eb emplace_back

using vi = vector<int>;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using ii = pair<int, int>;

#define fst first
#define snd second

const int MAX_N = 1e5 + 9;
 
int timer = 0;
stack<int> st;
bool vis[MAX_N];
int val[MAX_N], low[MAX_N];
vi adj[MAX_N];
vector<vi> comps;
 
void dfs(int u, int p = -1) {
    vis[u] = true;
    val[u] = low[u] = ++timer;
    st.push(u);
    for (int v : adj[u]) if (v != p) {
        if (vis[v]) {
            low[u] = min(low[u], val[v]);
        } else {
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] >= val[u]) {
                vi cmp{u};
                while (cmp.empty() || cmp.back() != v) {
                    cmp.push_back(st.top());
                    st.pop();
                }
                comps.push_back(cmp);
            }
        }
    }
}

const int MAX_K = 19;

vi g[2 * MAX_N];
int up[MAX_K][2 * MAX_N];
int depth[2 * MAX_N];
bool done[2 * MAX_N];
int parent[2 * MAX_N];

void dfs2(int u, int p = -1, int d = 0) {
    up[0][u] = p, done[u] = true;
    parent[u] = p, depth[u] = d;
    for (int v : g[u]) if (v != p) {
        dfs2(v, u, d + 1);
    }
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    int diff = depth[u] - depth[v];
    forn(i, MAX_K) if (diff >> i & 1) u = up[i][u];
    if (u == v) return u;
    dforn(i, MAX_K) if (up[i][u] != up[i][v]) {
        u = up[i][u], v = up[i][v];
    }
    return up[0][u];
}

int dp1[2 * MAX_N], dp2[2 * MAX_N];

void dfs3(int u) {
    done[u] = true;
    for (int v : g[u]) if (v != parent[u]) {
        if (!done[v]) dfs3(v);
        dp1[u] += dp1[v];
        dp2[u] += dp2[v];
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int n, m;
    cin >> n >> m;
    map<ii, int> id, cnt;
    forn(i, m) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        adj[u].pb(v);
        adj[v].pb(u);
        id[{u, v}] = i;
        cnt[minmax(u, v)]++;
    }
    forn(u, n) if (!vis[u]) dfs(u);
    vector<ii> bridges;
    forn(i, sz(comps)) {
        vi &cmp = comps[i];
        if (sz(cmp) == 1) continue;
        if (sz(cmp) == 2) {
            int u = cmp[0], v = cmp[1];
            if (cnt[minmax(u, v)] == 1) {
                if (!id.count(ii{u, v})) swap(u, v);
                bridges.eb(u, v);
                g[u].pb(v), g[v].pb(u);
                continue;
            }
        }
        for (int u : cmp) {
            g[n + i].pb(u);
            g[u].pb(n + i);
        }
    }
    forn(u, n + sz(comps)) {
        if (!done[u]) dfs2(u);
    }
    forn(i, MAX_K - 1) forn(j, n + sz(comps)) {
        if (up[i][j] == -1) up[i + 1][j] = -1;
        else up[i + 1][j] = up[i][up[i][j]];
    }
    int p;
    cin >> p;
    forn(i, p) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        int w = lca(u, v);
        dp1[u]++, dp2[v]++;
        dp1[w]--, dp2[w]--;
    }
    forn(u, n + sz(comps)) done[u] = false;
    forn(u, n + sz(comps)) {
        if (!done[u]) dfs3(u);
    }
    string ret(m, 'B');
    for (auto [u, v] : bridges) {
        int i = id[ii{u, v}];
        if (parent[u] == v) {
            if (dp1[u]) {
                ret[i] = 'R';
            } else if (dp2[u]) {
                ret[i] = 'L';
            }
        } else {
            assert(parent[v] == u);
            if (dp1[v]) {
                ret[i] = 'L';
            } else if (dp2[v]) {
                ret[i] = 'R';
            }
        }
    }
    cout << ret << '\n';
    
    return 0;
}

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