oj.uz

Submission #161687

# Submission time Handle Problem Language Result Execution time Memory
161687 2019-11-03T18:23:11 Z Minnakhmetov One-Way Streets (CEOI17_oneway) C++14
0 / 100
 235 ms 262148 KB 
#include <bits/stdc++.h>
    
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
 
using namespace std;

struct E {
    int to, i;
    bool straight;
};

const int N = 1e5 + 5, L = 19;
vector<E> g[N], g2[N], t[N];
int tin[N], mnt[N], tint[N], toutt[N], w[N][2], par[N][L],
    col[N];
int timer = 1;
string ans;

bool used[N];

void dfs(int node, int anc) {
    mnt[node] = tin[node] = timer++;

    for (E e : g[node]) {
        if (e.i != anc) {
            if (!tin[e.to]) {
                dfs(e.to, e.i);
                mnt[node] = min(mnt[node], mnt[e.to]);

                if (mnt[e.to] <= tin[node]) {
                    g2[node].push_back(e);
                    g2[e.to].push_back({node, e.i, e.straight ^ 1});
                }
            }
            else {
                mnt[node] = min(mnt[node], tin[e.to]);
                g2[node].push_back(e);
            }
        }
    }
}

void dive(int node, int c) {
    col[node] = c;

    for (E e : g2[node]) {
        if (col[e.to] == -1) {
            dive(e.to, c);
        }
    }

    for (E e : g[node]) {
        if (col[e.to] != -1 && col[e.to] != col[node]) {
            t[col[node]].push_back({col[e.to], e.i, e.straight});
            t[col[e.to]].push_back({col[node], e.i, e.straight ^ 1});
        }
    }
}


// bool used2[N];
void walk(int node) {
    // if (used2[node]) {
    //     cout << "AAA" << endl;
    //     exit(0);
    // }
    // used2[node] = 1;
    if (tint[node])
        return;

    tint[node] = ++timer;
    for (int i = 1; i < L; i++) {
        par[node][i] = par[par[node][i - 1]][i - 1];
    }

    for (E e : t[node]) {
        if (e.to != par[node][0]) {
            par[e.to][0] = node;
            walk(e.to);
        }
    }

    toutt[node] = timer;
}

bool upper(int a, int b) {
    return tint[a] <= tint[b] && toutt[a] >= toutt[b];
}

int getLca(int a, int b) {
    if (upper(a, b))
        return a;
    for (int i = L - 1; i >= 0; i--) {
        if (!upper(par[a][i], b))
            a = par[a][i];
    }
    return par[a][0];
}

void roam(int node) {
    used[node] = 1;
    for (E e : t[node]) {
        if (e.to != par[node][0]) {
            roam(e.to);
            if (w[e.to][0]) {
                ans[e.i] = (e.straight ? 'L' : 'R');
            }
            else if (w[e.to][1]) {
                ans[e.i] = (e.straight ? 'R' : 'L');
            }
            w[node][0] += w[e.to][0];
            w[node][1] += w[e.to][1];
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    int n, m, p;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        g[a].push_back({b, i, true});
        g[b].push_back({a, i, false});
    }


    dfs(0, -1);

    fill(col, col + n, -1);
    int cc = 0;

    for (int i = 0; i < n; i++) {
        if (col[i] == -1) {
            dive(i, cc++);
        }
    }

    for (int i = 0; i < cc; i++) {
        if (!tint[i]) {
            fill(par[i], par[i] + L, i);
            walk(i);
        }
    }

    ans.resize(m, 'B');

    cin >> p;

    for (int i = 0; i < p; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;

        a = col[a];
        b = col[b];

        int lca = getLca(a, b);

        w[a][0]++;
        w[lca][0]--;
        w[b][1]++;
        w[lca][1]--;
    }

    for (int i = 0; i < cc; i++) {
        if (!used[i])
            roam(i);
    }

    cout << ans;

    return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 235 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 235 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 235 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -