Submission #1180951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180951		Lithanium	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	122 ms	20204 KiB

oneway

#include <bits/stdc++.h>
using namespace std;

vector<int> adj[100005];
vector<pair<int, int>> cact[100005];
int dsu[100005], dt[100005][2];
bool seen[100005];
pair<int, int> up[100005];
int reach[100005];
int tot[100005];
int ans[100005]; // 1 -> R, 2 -> L

int find(int n) {
    if (dsu[n] == n) return n;
    return dsu[n] = find(dsu[n]);
}

void merge(int a, int b) {
    dsu[find(a)] = find(b);
}

void dfs(int n, int f, int d = 1) {
    seen[n] = 1;
    reach[n] = d;
    int freq = 0;
    for (int i:adj[n]) {
        if (i != f) {
            if (!reach[i]) dfs(i, n, d+1);
            reach[n] = min(reach[n], reach[i]);
        } else {
            if (freq) reach[n] = min(reach[n], reach[i]);
            freq = 1;
        }
    }
    if (reach[n] < d) merge(n, f);
}

vector<int> order;

void c(int n, int f) {
    seen[n] = 1;
    for (auto [i, j]:cact[n]) if (i != f) {
        up[i] = {n, j};
        c(i, n);
    }
    order.push_back(n);
}

int main() {
    int N, M;
    cin >> N >> M;
    for (int i = 1; i <= M; i ++) {
        cin >> dt[i][0] >> dt[i][1];
        int a = dt[i][0], b = dt[i][1];
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for (int i = 1; i <= N; i ++) dsu[i] = i;
    for (int i = 1; i <= N; i ++) if (!seen[i]) {
        dfs(i, 0);
    }
    memset(seen, 0, sizeof(seen));
    for (int i = 1; i <= M; i ++) {
        int a = dt[i][0], b = dt[i][1];
        if (find(a) != find(b)) {
            cact[find(a)].push_back({find(b), i});
            cact[find(b)].push_back({find(a), i});
        }
    }
    int Q;
    cin >> Q;
    while (Q --) {
        int a, b;
        cin >> a >> b;
        if (find(a) != find(b)) {
            tot[find(a)] ++, tot[find(b)] --;
        }
    }
    for (int i = 1; i <= N; i ++) if (!seen[find(i)]) {
        order.clear();
        c(find(i), 0);
        for (int node:order) if (node != find(i)) {
            if (tot[node] > 0) {
                // move up
                int a = dt[up[node].second][0];
                if (find(a) == node) ans[up[node].second] = 1;
                else ans[up[node].second] = 2;
            } else if (tot[node] < 0) {
                int a = dt[up[node].second][0];
                if (find(a) == node) ans[up[node].second] = 2;
                else ans[up[node].second] = 1;
            }
            tot[up[node].first] += tot[node];
        }
    }
    for (int i = 1; i <= M; i ++) {
        if (ans[i] == 1) cout << "R";
        else if (ans[i] == 2) cout << "L";
        else cout << "B";
    }
}

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