Submission #522226

#	Time	Username	Problem	Language	Result	Execution time	Memory
522226		huB1erTi2	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	1 ms	332 KiB

oneway

//   _|                                                _|
//   _|  _|    _|    _|    _|_|    _|_|_|      _|_|_|  _|  _|      _|_|      _|_|
//   _|_|      _|    _|  _|_|_|_|  _|    _|  _|_|      _|_|      _|_|_|_|  _|_|_|_|
//   _|  _|    _|    _|  _|        _|    _|      _|_|  _|  _|    _|        _|
//   _|    _|    _|_|_|    _|_|_|  _|_|_|    _|_|_|    _|    _|    _|_|_|    _|_|_|
//                   _|            _|
//               _|_|              _|
#include <iostream>
#include <vector>
#include <numeric>
#include <cassert>

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;
vec<int> tin;
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];
    bool dup = 0;
    for (auto [c, _] : g[v]) {
        if (c == p && !dup) {
            dup = 1;
            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]);
        }
    }
}

int compidx = -1;
vec<int> euler;
void compdfs(int v, int p, int idx, bool n) {
    if (n) {
        euleridx[idx] = euler.size();
        euler.pb(idx);
    }
    which[v] = idx;
    used[v] = 1;
    df("%d [%d]\n", v, idx);
    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;
            
            depth[nidx] = depth[idx]+1;
            parent[nidx] = {idx, -i};
            
            compdfs(c, v, nidx, 1);
            euler.pb(idx);
        } else {
            compdfs(c, v, idx, 0);
        }
    }
}

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;
}

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);
    which.resize(n);
    tin.resize(n);
    used.resize(n);
    low.resize(n);
    euleridx.resize(n);
    skip.resize(n, -1);
    parent.resize(n);
    ans.resize(m+1);
    depth.resize(n);
    
    foru (i, 20) {
        assert(log2(1 << i) == i);
    }
    
    foru (i, m) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        g[a].pb({b, i+1});
        g[b].pb({a, -(i+1)});
    }
    
    for (int i = 0; i < n; ++i) {
        if (!used[i]) lowdfs(i, i); 
    }
    used.assign(n, 0);
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            compdfs(i, i, ++compidx, 1);
        }
    }
    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];
        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;
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:24:11: warning: unused variable 'first' [-Wunused-variable]
   24 | #define x first
      |           ^~~~~
oneway.cpp:201:15: note: in expansion of macro 'x'
  201 |     for (auto x : euler) df("%d ", x);
      |               ^
oneway.cpp:24:11: warning: unused variable 'first' [-Wunused-variable]
   24 | #define x first
      |           ^~~~~
oneway.cpp:204:15: note: in expansion of macro 'x'
  204 |     for (auto x : euleridx) df("%d ", x);
      |               ^

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40