oj.uz

Submission #1003315

# Submission time Handle Problem Language Result Execution time Memory
1003315 2024-06-20T08:54:38 Z coolboy19521 One-Way Streets (CEOI17_oneway) C++17
0 / 100
 7 ms 10632 KB 
#pragma GCC optimize("Ofast")
#include"bits/stdc++.h"
#define int long long

using namespace std;

const int sz = 2e5 + 10;
const int sm = 25;

vector<vector<int>> aj[sz], ajgr[sz];
int br[sz], gr[sz], dp[sz];
int in[sz], lo[sz];
int pn[sz], pe[sz];
int le[sz], ri[sz];
int up[sm][sz];
int n, m, p;
bool dr[sz];
char la[sz];
int tr;

void taj(int v, int p = 0) {
    in[v] = lo[v] = ++ tr;
    bool ps = false;
    for (auto& u : aj[v]) {
        int to = u[0], nm = u[1];
        if (to == p && !ps) {
            ps = true;
            continue;
        } else if (in[to]) {
            lo[v] = min(lo[v], in[to]);
        } else {
            taj(to, v);
            lo[v] = min(lo[v], lo[to]);
            if (lo[to] > in[v]) {
                br[nm] = true;
            }
        }
    }
}

void cmp(int v, int gn) {
    gr[v] = gn;
    for (auto& u : aj[v]) {
        int to = u[0], nm = u[1];
        if (!gr[to] && !br[nm]) {
            cmp(to, gn);
        }
    }
}

void dpt(int v, int p = 0, int d = 1) {
    up[0][v] = pn[v];
    dp[v] = d;
    for (auto& u : ajgr[v]) {
        int to = u[0], nm = u[1];
        if (to != p) {
            pn[to] = v;
            pe[to] = nm;
            dpt(to, v, d + 1);
        }
    }
}

int lca(int a, int b) {
    if (dp[a] > dp[b]) {
        swap(a, b);
    }
    int d = dp[b] - dp[a];
    for (int i = 0; i < sm; i ++) {
        if (d & (1ll << i)) {
            b = up[i][b];
        }
    }
    if (a == b) {
        return a;
    }
    for (int i = 0; i < sm; i ++) {
        if (up[i][a] != up[i][b]) {
            a = up[i][a];
            b = up[i][b];
        }
    }
    return up[0][a];
}

void gdr(int a, int b, int d) {
    if (a == b) {
        return;
    }
    if (!dr[a]) {
        dr[a] = true;
        int to = pn[a];
        int nm = pe[a];
        int gna = gr[le[nm]];
        if (0 == d) {
            if (gna == a) {
                la[nm] = 'R';
            } else {
                la[nm] = 'L';
            }
        } else {
            if (gna == a) {
                la[nm] = 'L';
            } else {
                la[nm] = 'R';
            }
        }
        gdr(to, b, d);
    }
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    cin >> n >> m;

    for (int i = 1; i <= m; i ++) {
        int a, b;
        cin >> a >> b;

        aj[a].push_back({b, i});
        aj[b].push_back({a, i});
        le[i] = a;
        ri[i] = b;
        la[i] = 'B';
    }

    for (int i = 1; i <= n; i ++) {
        if (!in[i]) {
            taj(i);
        }
    }

    int gn = 0;

    for (int i = 1; i <= n; i ++) {
        if (!gr[i]) {
            cmp(i, ++ gn);
        }
    }

    for (int i = 1; i <= m; i ++) {
        if (br[i]) {
            int gna = gr[le[i]];
            int gnb = gr[ri[i]];
            ajgr[gna].push_back({gnb, i});
            ajgr[gnb].push_back({gna, i});
        }
    }

    for (int i = 1; i <= gn; i ++) {
        if (!dp[i]) {
            dpt(i);
        }
    }

    for (int i = 1; i < sm; i ++) {
        for (int j = 1; j <= gn; j ++) {
            up[i][j] = up[i - 1][up[i - 1][j]];
        }
    }

    vector<vector<int>> ord;

    int q;
    cin >> q;

    while (q --) {
        int a, b;
        cin >> a >> b;

        a = gr[a];
        b = gr[b];
        int l = lca(a, b);
        ord.push_back({dp[l], a, b, l});
    }

    sort(begin(ord), end(ord));

    for (auto& i : ord) {
        int a = i[1];
        int b = i[2];
        int l = i[3];
        gdr(a, l, 0);
        gdr(b, l, 1);
    }

    for (int i = 1; i <= m; i ++) {
        cout << la[i];
    }

    cout << '\n';
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10076 KB Output is correct
2 Correct 7 ms 10076 KB Output is correct
3 Correct 5 ms 10332 KB Output is correct
4 Incorrect 5 ms 10632 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10076 KB Output is correct
2 Correct 7 ms 10076 KB Output is correct
3 Correct 5 ms 10332 KB Output is correct
4 Incorrect 5 ms 10632 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10076 KB Output is correct
2 Correct 7 ms 10076 KB Output is correct
3 Correct 5 ms 10332 KB Output is correct
4 Incorrect 5 ms 10632 KB Output isn't correct
5 Halted 0 ms 0 KB -