Submission #151734

#	Time	Username	Problem	Language	Result	Execution time	Memory
151734		forestryks	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	9 ms	5496 KiB

oneway

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
#define rep(i, n) for (int (i) = 0; (i) < (n); ++(i))
#define all(x) (x).begin(), (x).end()
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

struct edge {
    int u, v, id;
};

const int MAXN = 1e5 + 5;
int n, m;
vector<edge> e;
vector<int> g[MAXN];
int tt = 0;
int tin[MAXN];
int fup[MAXN];
bool used[MAXN];

int dsu[MAXN];
int sz[MAXN];

void init() {
    rep(i, n) {
        dsu[i] = i;
        sz[i] = 1;
    }
}

int get(int v) {
    if (dsu[v] == v) return v;
    return (dsu[v] = get(dsu[v]));
}

void merge(int u, int v) {
    u = get(u);
    v = get(v);
    if (u == v) return;
    if (sz[u] < sz[v]) swap(u, v);
    dsu[v] = u;
    sz[u] += sz[v];
}

void dfs(int v, int p) {
    tin[v] = fup[v] = tt++;
    used[v] = true;
    for (auto to : g[v]) {
        if (to == p) continue;
        if (used[to]) {
            fup[v] = min(fup[v], tin[to]);
        } else {
            dfs(to, v);
            if (fup[to] > tin[v]) {
                // bridge
            } else {
                fup[v] = min(fup[v], fup[to]);
                merge(v, to);
            }
        }
    }
}

int p[MAXN];
int h[MAXN];
int tout[MAXN];
int up[MAXN][20];

void pre(int v) {
    used[v] = true;
    if (p[v] == -1) up[v][0] = v;
    else up[v][0] = p[v];
    for (int i = 1; i < 20; ++i) {
        up[v][i] = up[up[v][i - 1]][i - 1];
    }

    tin[v] = tt++;
    for (auto to : g[v]) {
        g[to].erase(find(all(g[to]), v));
        p[to] = v;
        h[to] = h[v] + 1;
        pre(to);
    }
    tout[v] = tt++;
}

int lca(int u, int v) {
    if (tin[u] <= tin[v] && tin[v] < tout[u]) return u;
    for (int i = 19; i >= 0; --i) {
        if (!(tin[up[u][i]] <= tin[v] && tin[v] < tout[up[u][i]])) {
            u = up[u][i];
        }
    }
    return p[u];
}

int eup[MAXN];
int edown[MAXN];

void post(int v) {
    used[v] = true;
    for (auto to : g[v]) {
        post(to);
        eup[v] = max(eup[v], eup[to] - 1);
        edown[v] = max(edown[v], edown[to] - 1);
    }
}

int main() {
    FAST_IO;
    cin >> n >> m;
    rep(i, m) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        g[u].push_back(v);
        g[v].push_back(u);
        e.push_back({u, v, i});
    }

    init();
    rep(i, n) {
        if (!used[i]) {
            dfs(i, -1);
        }
    }

    rep(i, n) {
        g[i].clear();
    }

    map<int, int> cc;

    rep(i, n) {
        dsu[i] = get(i);
    }

    rep(i, n) {
        if (cc.find(dsu[i]) == cc.end()) {
            int id = cc.size();
            cc[dsu[i]] = id;
        }
        dsu[i] = cc[dsu[i]];
    }

    // rep(i, n) {
    //     cout << dsu[i] << ' ';
    // }
    // cout << endl;

    rep(i, m) {
        int &u = e[i].u, &v = e[i].v;
        u = dsu[u]; v = dsu[v];
        // cout << u << ' ' << v << endl;
        if (u == v) continue;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    tt = 0;
    p[0] = -1;
    fill(used, used + cc.size(), false);
    vector<int> roots;
    rep(i, cc.size()) {
        if (!used[i]) {
            pre(i);
            roots.push_back(i);
        }
    }
    // pre(0);

    // return 0;

    int k;
    cin >> k;
    rep(i, k) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        u = dsu[u];
        v = dsu[v];
        if (u == v) continue;

        int lc = lca(u, v);

        if (u != lc) {
            eup[u] = max(eup[u], h[u] - h[lc]);
        }
        if (v != lc) {
            edown[v] = max(edown[v], h[v] - h[lc]);
        }
    }

    for (auto v : roots) {
        post(v);
    }

    rep(i, m) {
        int u = e[i].u, v = e[i].v;
        if (u == v) {
            cout << 'B';
            continue;
        }
        bool sw = false;
        if (p[v] == u) {
            sw = true;
            swap(u, v);
        }

        // p[u] == v

        if (!edown[u] && !eup[u]) {
            cout << 'B';
            continue;
        }

        if (edown[u]) {
            sw ^= 1;
        }

        cout << "RL"[sw];
    }
    cout << endl;
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:7:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int (i) = 0; (i) < (n); ++(i))
                                     ~~~~^~~~~
oneway.cpp:167:5: note: in expansion of macro 'rep'
     rep(i, cc.size()) {
     ^~~

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