oj.uz

Submission #855927

# Submission time Handle Problem Language Result Execution time Memory
855927 2023-10-02T09:53:33 Z thanh913 One-Way Streets (CEOI17_oneway) C++14
0 / 100
 149 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define ll long long

const int N = 2e5+5;

//-------------------------------
int n, m, p;
int isBridge[N];
pair<int, int> edge[N], need[N];
vector<pair<int, int>> adj[N];

vector<pair<pair<int, int>, int>> tmp;
void init() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        edge[i] = {u, v};
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
        tmp.push_back({edge[i], i});
    }
    cin >> p;
    for (int i = 1; i <= p; i++) {
        cin >> need[i].fi >> need[i].se;
    }
    sort(tmp.begin(), tmp.end());
    for (int i = 1; i < m; i++) {
        if (tmp[i].fi == tmp[i-1].fi) {
            isBridge[tmp[i].se] = isBridge[tmp[i-1].se] = -1;
        }
    }
}

int timer, num[N], low[N];
void dfs(int u, int pr) {
    num[u] = low[u] = ++timer;
    for (auto e : adj[u]) {
        int v, idx; tie(v, idx) = e;
        if (v == pr) continue;
        if (num[v]) {
            low[u] = min(low[u], num[v]);
            continue;
        }
        dfs(v, u);
        low[u] = min(low[u], low[v]);
        if (low[v] == num[v] && isBridge[idx] != -1)
            isBridge[idx] = 1;
    }
}

int cc, ins[N];
vector<pair<int, int>> tree[N];
void nen(int u) {
    ins[u] = cc;
    for (auto e : adj[u]) {
        int v, idx; tie(v, idx) = e;
        if (isBridge[idx] == 1 || ins[v]) continue;
        nen(v);
    }
}

//xu ly tren cay

int tin[N], tout[N];
bool isAnc(int u, int v) {
    return (tin[u] <= tin[v] && tout[u] >= tout[v]);
}

int up[N]; pair<int, int> cha[N];
int find(int u) {
    return ((u == up[u]) ? u : (up[u] = find(up[u])));
}

void dfs2(int u, int pr) {
    up[u] = u;
    tin[u] = ++timer;
    for (auto e : tree[u]) {
        if (e.fi != pr) {
            cha[e.fi] = {u, e.se};
            dfs2(e.fi, u);
        }
    }
    tout[u] = timer;
}

int ans[N];

void solve() {
    for (int i = 1; i <= n; i++) {
        if (!num[i]) dfs(i, i);
    }
    for (int i = 1; i <= n; i++) {
        if (ins[i]) continue;
        cc++; nen(i);
    }
    for (int i = 1; i <= m; i++) {
        if (isBridge[i] != 1) continue;
        int u, v; tie(u, v) = edge[i];
        u = ins[u]; v = ins[v];
        tree[u].push_back({v, i});
        tree[v].push_back({u, i});
    }
    timer = 0;
    for (int i = 1; i <= cc; i++) {
        if (!tin[i]) dfs2(i, i);
    }
    for (int i = 1; i <= p; i++) {
        int u, v; tie(u, v) = need[i];
        u = ins[u]; v = ins[v];
        int cur = u;
        while (!isAnc((cur = find(cur)), v)) {
            int idx, pr; tie(pr, idx) = cha[cur];
            if (make_pair(cur, pr) == make_pair(ins[edge[idx].fi], ins[edge[idx].se]))
                ans[idx] = 2;
            else
                ans[idx] = 1;
            up[cur] = up[pr];
        }

        cur = v;
        while (!isAnc((cur = find(cur)), u)) {
            int idx, pr; tie(pr, idx) = cha[cur];
            if (make_pair(cur, pr) == make_pair(ins[edge[idx].fi], ins[edge[idx].se]))
                ans[idx] = 1;
            else
                ans[idx] = 2;
            up[cur] = up[pr];
        }
    }
    for (int i = 1; i <= m; i++) {
        if (isBridge[i] == 1) {
            if (ans[i] == 0) cout << 'B';
            if (ans[i] == 1) cout << 'L';
            if (ans[i] == 2) cout << 'R';
        }
        else cout << 'B';
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    init();
    solve();
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16728 KB Output is correct
2 Correct 3 ms 16728 KB Output is correct
3 Correct 3 ms 16732 KB Output is correct
4 Correct 4 ms 16984 KB Output is correct
5 Correct 3 ms 16984 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct
8 Correct 3 ms 16988 KB Output is correct
9 Runtime error 149 ms 262144 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16728 KB Output is correct
2 Correct 3 ms 16728 KB Output is correct
3 Correct 3 ms 16732 KB Output is correct
4 Correct 4 ms 16984 KB Output is correct
5 Correct 3 ms 16984 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct
8 Correct 3 ms 16988 KB Output is correct
9 Runtime error 149 ms 262144 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16728 KB Output is correct
2 Correct 3 ms 16728 KB Output is correct
3 Correct 3 ms 16732 KB Output is correct
4 Correct 4 ms 16984 KB Output is correct
5 Correct 3 ms 16984 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct
8 Correct 3 ms 16988 KB Output is correct
9 Runtime error 149 ms 262144 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -