oj.uz

Submission #312898

# Submission time Handle Problem Language Result Execution time Memory
312898 2020-10-14T14:43:29 Z jungsnow One-Way Streets (CEOI17_oneway) C++14
0 / 100
 5 ms 5248 KB 
#include<bits/stdc++.h>
#define x first
#define y second
#define eb emplace_back

using namespace std;

struct edge {
    int u, v, id;

    edge(int u, int v, int id) : u(u), v(v), id(id) {}

    edge() {}
};

typedef pair<int, int> ii;

const int N = 100100;

int n, m, q, timer, tin[N], low[N];
int p[N], par[N][20], dep[N], above[N][2];
int req[N][3];
char ans[N];
vector<ii> g[N], gc[N], ed, ord;
vector<edge> br;

int root(int u) {
    return (p[u] == u ? u : p[u] = root(p[u]));
}

void merge(int u, int v) {
    u = root(u);
    v = root(v);
    if (u == v) return;
    p[v] = u;
}

void dfs(int u, int pre = -1) {
    tin[u] = low[u] = ++timer;
    for (ii e : g[u]) {
        int v = e.x; if (v == pre) continue;
        if (~tin[v]) {
            low[u] = min(low[u], tin[v]);
        } else {
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] > tin[u])
                br.eb(u, v, e.y);
            else merge(u, v);
        }
    }
}

void redfs(int u, int pre = -1) {
    par[u][0] = pre;
    for (int i = 1; i < 20; ++i) {
        par[u][i] = par[ par[u][i - 1] ][i - 1];
    }
    for (ii e : gc[u]) if (e.x != pre) {
        int v = e.x;
        dep[v] = dep[u] + 1;
        above[v][0] = u;
        above[v][1] = e.y;
        redfs(v, u);
    }
}

int jump(int u, int h) {
    for (int i = 20; i + 1; --i) if (h >= (1 << i)) {
        h -= (1 << i);
        u = par[u][i];
    }
    return u;
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    u = jump(u, dep[u] - dep[v]);
    if (u == v) return u;
    for (int i = 19; i + 1; --i) {
        if (par[u][i] != par[v][i]) {
            u = par[u][i];
            v = par[v][i];
        }
    }
    return par[u][0];
}

void direct(int u, int v, bool up) {
    if (u == v) return;
    int y = above[u][0], id = above[u][1];
    if (ans[id] != 'B') return;
    int a = root(ed[id].x), b = root(ed[id].y);
    if (up) { /// u->y;
        if (a == u && b == y) ans[id] = 'R'; else ans[id] = 'L';
    } else { /// y->u;
        if (a == y && b == u) ans[id] = 'R'; else ans[id] = 'L';
    }
    direct(y, v, up);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("oneway.in", "r", stdin);
//    freopen("oneway.out", "w", stdout);
    cin>>n>>m;
    for (int u, v, i = 0; i < m; ++i) {
        cin>>u>>v;
        g[u].eb(v, i);
        g[v].eb(u, i);
        ed.eb(u, v);
    }
    fill(ans, ans + m, 'B');
    fill(tin + 1, tin + 1 + n, -1);
    fill(dep + 1, dep + 1 + n, -1);
    for (int i = 1; i <= n; ++i) p[i] = i;
    for (int i = 1; i <= n; ++i) if (tin[i] == -1)
        dfs(i);
    for (edge e : br) {
        int u = root(e.u), v = root(e.v);
        gc[u].eb(v, e.id);
        gc[v].eb(u, e.id);
    }
    for (int i = 1; i <= n; ++i) if (root(i) == i && dep[i] == -1)
        redfs(i);
    cin>>q;
    for (int u, v, i = 1; i <= q; ++i) {
        cin>>u>>v;
        u = root(u);
        v = root(v);
        req[i][0] = u;
        req[i][1] = v;
        req[i][2] = lca(u, v);
        ord.eb(dep[ req[i][2] ], i);
    }
    sort(ord.begin(), ord.end());
    for (ii e : ord) {
        int id = e.y;
        int u = req[id][0], v = req[id][1], w = req[id][2];
        direct(u, w, 1);
        direct(v, w, 0);
    }
    for (int i = 0; i < m; ++i) cout<<ans[i];
    return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 4 ms 5120 KB Output is correct
3 Correct 4 ms 5248 KB Output is correct
4 Correct 4 ms 5248 KB Output is correct
5 Correct 4 ms 5248 KB Output is correct
6 Correct 4 ms 5120 KB Output is correct
7 Correct 4 ms 5248 KB Output is correct
8 Correct 5 ms 5248 KB Output is correct
9 Incorrect 4 ms 5120 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 4 ms 5120 KB Output is correct
3 Correct 4 ms 5248 KB Output is correct
4 Correct 4 ms 5248 KB Output is correct
5 Correct 4 ms 5248 KB Output is correct
6 Correct 4 ms 5120 KB Output is correct
7 Correct 4 ms 5248 KB Output is correct
8 Correct 5 ms 5248 KB Output is correct
9 Incorrect 4 ms 5120 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 4 ms 5120 KB Output is correct
3 Correct 4 ms 5248 KB Output is correct
4 Correct 4 ms 5248 KB Output is correct
5 Correct 4 ms 5248 KB Output is correct
6 Correct 4 ms 5120 KB Output is correct
7 Correct 4 ms 5248 KB Output is correct
8 Correct 5 ms 5248 KB Output is correct
9 Incorrect 4 ms 5120 KB Output isn't correct
10 Halted 0 ms 0 KB -