oj.uz

답안 #521612

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
521612 2022-02-02T14:39:53 Z huB1erTi2 One-Way Streets (CEOI17_oneway) C++17
0 / 100
 1 ms 460 KB 
//   _|                                                _|
//   _|  _|    _|    _|    _|_|    _|_|_|      _|_|_|  _|  _|      _|_|      _|_|
//   _|_|      _|    _|  _|_|_|_|  _|    _|  _|_|      _|_|      _|_|_|_|  _|_|_|_|
//   _|  _|    _|    _|  _|        _|    _|      _|_|  _|  _|    _|        _|
//   _|    _|    _|_|_|    _|_|_|  _|_|_|    _|_|_|    _|    _|    _|_|_|    _|_|_|
//                   _|            _|
//               _|_|              _|
#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

// #define DEBUG
#ifdef DEBUG
#define dassert(x) assert(x);
#define df(...) printf(__VA_ARGS__)
#else
#define dassert(x)
#define df(...)
#endif

#define x first
#define y second
#define mp make_pair
#define pb push_back
#define ir(x, a, b) ((a) <= (x) && (x) <= (b))
#define vec vector
#define sz(x) (ll)x.size()
#define foru(i, n) for (int i = 0; (i) < (n); ++(i))
#define all(x) (x).begin(), (x).end()

typedef int64_t ll;

int read() {
    int n = 0; bool b = 0; char c = getchar();
    for (; !ir(c, '0', '9'); c = getchar()) b = (c == '-');
    for (; ir(c, '0', '9'); c = getchar()) n = 10*n + (c-'0');
    if (b) return -n;
    return n;
}

vec<char> used;
vec<vec<pair<int, int>>> g, g_;
vec<int> tin, tout;
vec<int> low;
vec<char> set;
vec<int> which;
vec<int> depth;
vec<int> ans;
vec<int> skip;
vec<pair<int, int>> parent;
vec<int> euleridx;
int lca[int(2e5+100)][40];

int _t = 0;

void lowdfs(int v, int p) {
    used[v] = 1;
    tin[v] = _t++;
    low[v] = tin[v];
    for (auto [c, _] : g[v]) {
        if (c == p) continue;
        if (used[c]) {
            df("back edge %d-%d\n", v, c);
            low[v] = min(low[v], tin[c]);
        } else {
            lowdfs(c, v);
            low[v] = min(low[v], low[c]);
        }
    }
    tout[v] = _t;
}

int compidx = 0;
vec<vec<int>> components;
vec<int> euler = {0};
void compdfs(int v, int p, int idx) {
    df("%d [%d]\n", v, idx);
    used[v] = 1;
    which[v] = idx;
    components[idx].pb(v);
    for (auto [c, i] : g[v]) {
        if (used[c] || c == p) continue;
        if (tin[c] == low[c]) {
            df("bridge %d->%d\n", v, c);
            int nidx = ++compidx;
            euleridx[nidx] = euler.size();
            depth[nidx] = depth[idx]+1;
            parent[nidx] = {idx, -i};
            euler.pb(nidx);
            g_[idx].pb({nidx, i});
            g_[nidx].pb({idx, -i});
            compdfs(c, v, nidx);
            euler.pb(idx);
        } else {
            compdfs(c, v, idx);
        }
    }
}

void calclca() {
    int n = euler.size();
    for (int i = 0; i < n; ++i) {
        lca[0][i] = euler[i];
    }
    for (int k = 1; (1 << k) <= n; ++k) {
        for (int i = 0; i + (1 << k) <= n; ++i) {
            lca[k][i] = lca[k-1][i + (1 << (k-1))];
            if (depth[lca[k-1][i]] < depth[lca[k][i]]) {
                lca[k][i] = lca[k-1][i];
            }
        }
    }
}

int log2(int x) {
    return 31 - __builtin_clz(x);
}

int getlca(int x, int y) {
    x = euleridx[x], y = euleridx[y];
    if (y < x) swap(x, y);
    int len = y-x+1, k = log2(len), alen = (1 << k);
    int ans = lca[k][y - alen + 1];
    if (depth[lca[k][x]] < depth[ans]) ans = lca[k][x];
    return ans;
}

int sign(int x) {
    if (x < 0) return -1;
    return 1;
}

void setroad(int v, int anc, int set) {
    df("going %d {%d}\n", v, depth[v]);
    while (depth[v] > depth[anc]) {
        int go = skip[v];
        if (go == -1) {
            int i = parent[v].y;
            go = parent[v].x;
            skip[v] = anc;
            
            if (i < 0) {
                ans[-i] = -set;
            } else {
                ans[i] = set;
            }
        } else {
            if (depth[anc] < depth[skip[v]]) {
                skip[v] = anc;
            }
        }
        df("%d-->%d\n", v, go);
        v = go;
    }
}

int main() {
    df("debug mode\n");
#ifndef DEBUG
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif
    int n, m;
    cin >> n >> m;
    
    g.resize(n);
    g_.resize(n);
    which.resize(n);
    components.resize(n);
    tin.resize(n);
    tout.resize(n);
    used.resize(n);
    low.resize(n);
    euleridx.resize(n);
    skip.resize(n, -1);
    parent.resize(n);
    ans.resize(n+1);
    depth.resize(n);
    
    foru (i, m) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        g[a].pb({b, i+1});
        g[b].pb({a, -(i+1)});
    }
    
    lowdfs(0, 0); used.assign(n, 0);
    compdfs(0, 0, 0); used.assign(n, 0);
    swap(g, g_);
    calclca();
    
    // df("euler: ");
    // for (auto x : euler) df("%d ", x);
    // df("\n");
    // df("euleridx: ");
    // for (auto x : euleridx) df("%d ", x);
    // df("\n");
    int p;
    cin >> p;
    foru (i, p) {
        int a, b;
        cin >> a >> b;
        a = which[a-1], b = which[b-1];
        df("going %d to %d\n", a, b);
        int l = getlca(a, b);
        df("going %d to %d [lca: %d]\n", a, b, l);
        setroad(a, l, 1);
        setroad(b, l, -1);
    }
    for (int i = 1; i <= m; ++i) {
        if (ans[i] == 0) {
            cout << 'B';
        } else if (ans[i] == -1) {
            cout << 'L';
        } else {
            cout << 'R';
        }
    }
    cout << "\n";
    return 0;
}

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -