Submission #1180899

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180899		Lithanium	One-Way Streets (CEOI17_oneway)	C++20	0 / 100	3 ms	4928 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];
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) {
    reach[n] = d;
    for (int i:adj[n]) if (i != f) {
        if (!reach[i]) dfs(i, n, d+1);
        reach[n] = min(reach[n], reach[i]);
    }
    if (reach[n] < d) merge(n, f);
}

vector<int> order;

void c(int n, int f) {
    for (auto [i, j]:cact[n]) if (i != f) {
        up[i] = 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;
    dfs(1, 0);
    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});
        }
    }
    c(find(1), 0);
    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 node:order) if (node != find(1)) {
        if (tot[node] > 0) {
            // move up
            int a = dt[up[node]][0], b = dt[up[node]][1];
            if (find(a) == node) ans[up[node]] = 1;
            else ans[up[node]] = 2;
        } else if (tot[node] < 0) {
            int a = dt[up[node]][0], b = dt[up[node]][1];
            if (find(a) == node) ans[up[node]] = 2;
            else ans[up[node]] = 1;
        }
    }
    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: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40