oj.uz

Submission #510576

# Submission time Handle Problem Language Result Execution time Memory
510576 2022-01-15T01:57:08 Z Monarchuwu One-Way Streets (CEOI17_oneway) C++14
100 / 100
 192 ms 29556 KB 
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;

typedef pair<int, int> pii;
#define ff first
#define ss second

const int N = 1e5 + 9;
int n, m, p;
int a[N], b[N], x[N], y[N];
vector<int> g[N];

int num[N], low[N], tme;
int stk[N], top;
int lab[N], cnt_scc;
void tarjan(int u, int p) {
    num[u] = low[u] = ++tme;
    stk[++top] = u;
    for (int v : g[u]) {
        if (v == p) {
            p = 0;
            continue;
        }

        if (num[v]) low[u] = min(low[u], num[v]);
        else {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
        }
    }

    if (num[u] == low[u]) { // chot
        lab[u] = ++cnt_scc;
        while (stk[top] != u)
            lab[stk[top--]] = cnt_scc;
        --top;
    }
}

int h[N], par[N][17];
void dfs(int u) {
    sort(all(g[u]));
    for (int v : g[u]) if (v != par[u][0]) {
        h[v] = h[u] + 1;
        par[v][0] = u;
        for (int j = 1; (1 << j) <= h[v]; ++j)
            par[v][j] = par[par[v][j - 1]][j - 1];
        dfs(v);
    }
}
int st[N][17];
void gogo(int u, int v) {
    if (h[u] > h[v]) {
        int k = h[u] - h[v];
        for (int j = log2(k); ~j; --j)
            if (k >> j & 1) {
                st[u][j] |= 1; // u->par
                u = par[u][j];
            }
    }
    if (h[u] < h[v]) {
        int k = h[v] - h[u];
        for (int j = log2(k); ~j; --j)
            if (k >> j & 1) {
                st[v][j] |= 2; // par->v
                v = par[v][j];
            }
    }
    if (u == v) return;

    for (int j = log2(h[u]); ~j; --j)
        if (par[u][j] != par[v][j]) {
            st[u][j] |= 1;
            st[v][j] |= 2;
            u = par[u][j];
            v = par[v][j];
        }
    st[u][0] |= 1;
    st[v][0] |= 2;
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> a[i] >> b[i];
        g[a[i]].push_back(b[i]);
        g[b[i]].push_back(a[i]);
    }
    cin >> p;
    for (int i = 0; i < p; ++i)
        cin >> x[i] >> y[i];
    for (int i = 1; i <= n; ++i)
        if (!num[i]) tarjan(i, 0);

    for (int i = 1; i <= n; ++i) g[i].clear();
    for (int i = 0; i < m; ++i) if (lab[a[i]] != lab[b[i]]) {
        g[lab[a[i]]].push_back(lab[b[i]]);
        g[lab[b[i]]].push_back(lab[a[i]]);
    }
    fill(h + 1, h + cnt_scc + 1, -1);
    for (int i = 1; i <= cnt_scc; ++i)
        if (h[i] == -1) h[i] = 0, dfs(i);

    for (int i = 0; i < p; ++i) {
        if (lab[x[i]] != lab[y[i]])
            gogo(lab[x[i]], lab[y[i]]);
    }

    for (int j = 16; j; --j)
        for (int i = 1; i <= n; ++i) {
            st[i][j - 1] |= st[i][j];
            st[par[i][j - 1]][j - 1] |= st[i][j];
        }

    for (int i = 0, u, v; i < m; ++i) {
        u = lab[a[i]], v = lab[b[i]];
        if (u == v) cout << 'B';
        else {
            if (par[u][0] == v) {   // u->v
                cout << "BRL"[st[u][0]];
            }
            else {                  // v->u
                cout << "BLR"[st[v][0]];
            }
        }
    }
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 3 ms 2764 KB Output is correct
4 Correct 2 ms 2892 KB Output is correct
5 Correct 2 ms 2892 KB Output is correct
6 Correct 2 ms 2764 KB Output is correct
7 Correct 2 ms 2892 KB Output is correct
8 Correct 3 ms 2892 KB Output is correct
9 Correct 2 ms 2764 KB Output is correct
10 Correct 3 ms 2764 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 3 ms 2764 KB Output is correct
4 Correct 2 ms 2892 KB Output is correct
5 Correct 2 ms 2892 KB Output is correct
6 Correct 2 ms 2764 KB Output is correct
7 Correct 2 ms 2892 KB Output is correct
8 Correct 3 ms 2892 KB Output is correct
9 Correct 2 ms 2764 KB Output is correct
10 Correct 3 ms 2764 KB Output is correct
11 Correct 37 ms 8776 KB Output is correct
12 Correct 53 ms 10788 KB Output is correct
13 Correct 50 ms 13472 KB Output is correct
14 Correct 127 ms 18024 KB Output is correct
15 Correct 106 ms 19684 KB Output is correct
16 Correct 167 ms 23108 KB Output is correct
17 Correct 79 ms 24448 KB Output is correct
18 Correct 123 ms 23064 KB Output is correct
19 Correct 89 ms 25616 KB Output is correct
20 Correct 47 ms 11904 KB Output is correct
21 Correct 41 ms 11704 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 3 ms 2764 KB Output is correct
4 Correct 2 ms 2892 KB Output is correct
5 Correct 2 ms 2892 KB Output is correct
6 Correct 2 ms 2764 KB Output is correct
7 Correct 2 ms 2892 KB Output is correct
8 Correct 3 ms 2892 KB Output is correct
9 Correct 2 ms 2764 KB Output is correct
10 Correct 3 ms 2764 KB Output is correct
11 Correct 37 ms 8776 KB Output is correct
12 Correct 53 ms 10788 KB Output is correct
13 Correct 50 ms 13472 KB Output is correct
14 Correct 127 ms 18024 KB Output is correct
15 Correct 106 ms 19684 KB Output is correct
16 Correct 167 ms 23108 KB Output is correct
17 Correct 79 ms 24448 KB Output is correct
18 Correct 123 ms 23064 KB Output is correct
19 Correct 89 ms 25616 KB Output is correct
20 Correct 47 ms 11904 KB Output is correct
21 Correct 41 ms 11704 KB Output is correct
22 Correct 184 ms 26416 KB Output is correct
23 Correct 168 ms 24728 KB Output is correct
24 Correct 167 ms 25012 KB Output is correct
25 Correct 161 ms 29556 KB Output is correct
26 Correct 162 ms 26188 KB Output is correct
27 Correct 192 ms 24904 KB Output is correct
28 Correct 27 ms 6648 KB Output is correct
29 Correct 70 ms 13372 KB Output is correct
30 Correct 92 ms 13544 KB Output is correct
31 Correct 59 ms 13948 KB Output is correct
32 Correct 107 ms 18948 KB Output is correct