Submission #715272

#	Time	Username	Problem	Language	Result	Execution time	Memory
715272		dxz05	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	345 ms	57236 KiB

oneway

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define bpc(x) __builtin_popcount(x)
#define bpcll(x) __builtin_popcountll(x)
#define MP make_pair
//#define endl '\n'

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

typedef long long ll;
const int MOD = 1e9 + 7;
const int N = 2e5 + 3e2;

template<typename T>
struct fenwick{
    vector<T> f;
    fenwick(int n){
        f.resize(n + 2);
    }
    fenwick(){};
    void init(int n){
        f.resize(n + 2);
    }

    void add(int i, T val){
        i++;
        while (i < (int)f.size()){
            f[i] += val;
            i += -i & i;
        }
    }

    void add(int l, int r, T val){
        add(l, val);
        add(r + 1, -val);
    }

    T get(int i){
        i++;
        T res = 0;
        while (i > 0){
            res += f[i];
            i -= -i & i;
        }
        return res;
    }

    T get(int l, int r){
        if (l > r) return 0;
        return get(r) - get(l - 1);
    }
};

vector<pair<int, int>> g[N];

int fup[N], tin[N], timer;
bool used[N], bridge[N];
void dfs0(int v, int p){
    tin[v] = fup[v] = ++timer;

    used[v] = true;
    for (auto [c, i] : g[v]){
        if (c == p) continue;

        if (!used[c]){
            dfs0(c, v);
            fup[v] = min(fup[v], fup[c]);

            if (fup[c] > tin[v]){
                bridge[i] = true;
            }
        } else {
            fup[v] = min(fup[v], tin[c]);
        }

    }
}

int id[N];
void dfs1(int v, int _id){
    used[v] = true;
    id[v] = _id;
    for (auto [c, i] : g[v]){
        if (!used[c] && !bridge[i]) dfs1(c, _id);
    }
}

vector<int> g2[N];

int up[N][18];
int tout[N];
void dfs2(int v, int p){
    tin[v] = tout[v] = ++timer;

    up[v][0] = p;
    for (int i = 1; i < 18; i++){
        up[v][i] = up[up[v][i - 1]][i - 1];
    }

    for (int c : g2[v]){
        if (c != p){
            dfs2(c, v);
            tout[v] = tout[c];
        }
    }

}

bool upper(int p, int v){
    return tin[p] <= tin[v] && tout[v] <= tout[p];
}

int lca(int u, int v){
    if (upper(u, v)) return u;
    if (upper(v, u)) return v;
    for (int i = 17; i >= 0; i--){
        if (!upper(up[u][i], v)) u = up[u][i];
    }
    return up[u][0];
}

vector<int> upwards[N], downwards[N];
fenwick<int> fu(N), fd(N);

set<pair<int, int>> must;

void dfs3(int v, int p){
    for (int x : upwards[v]) fu.add(tin[x], 1);
    for (int x : downwards[v]) fd.add(tin[x], 1);

    for (int c : g2[v]){
        if (c != p){
            if (fu.get(tin[c], tout[c])) must.insert(MP(c, v));
            if (fd.get(tin[c], tout[c])) must.insert(MP(v, c));
            dfs3(c, v);
        }
    }
}

void solve(){
    int n, m;
    cin >> n >> m;

    vector<pair<int, int>> edges;
    for (int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;

        g[u].emplace_back(v, i);
        g[v].emplace_back(u, i);

        edges.emplace_back(u, v);
    }

    for (int i = 1; i <= n; i++){
        if (!used[i]) dfs0(i, -1);
    }

    map<pair<int, int>, int> mpe;
    for (int i = 0; i < m; i++){
        auto [u, v] = edges[i];
        if (u > v) swap(u, v);

        if (mpe.find(MP(u, v)) != mpe.end()){
            bridge[i] = false;
            bridge[mpe[(MP(u, v))]] = false;
        } else {
            mpe[MP(u, v)] = i;
        }

    }

    fill(used + 1, used + n + 1, false);

    int id_cnt = 0;
    for (int i = 1; i <= n; i++){
        if (!used[i]) dfs1(i, ++id_cnt);
    }

    for (int i = 0; i < m; i++){
        auto [u, v] = edges[i];
        u = id[u], v = id[v];

        if (bridge[i]){
            g2[u].emplace_back(v);
            g2[v].emplace_back(u);
        }
    }

    timer = 0;
    for (int i = 1; i <= id_cnt; i++){
        if (up[i][0] == 0){
            dfs2(i, i);
        }
    }

    int q;
    cin >> q;

    while (q--){
        int u, v;
        cin >> u >> v;
        u = id[u], v = id[v];

        int x = lca(u, v);

        if (x != u) upwards[x].push_back(u);
        if (x != v) downwards[x].push_back(v);
    }

    for (int i = 1; i <= id_cnt; i++){
        if (up[i][0] == i) dfs3(i, i);
    }

    for (int i = 0; i < m; i++){
        auto [u, v] = edges[i];
        u = id[u], v = id[v];

        char ch = 'B';
        if (must.find(MP(u, v)) != must.end()) ch = 'R';
        if (must.find(MP(v, u)) != must.end()) ch = 'L';

        cout << ch;
    }

    cout << endl;

}

int main(){
    clock_t startTime = clock();
    ios_base::sync_with_stdio(false);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int test_cases = 1;
//    cin >> test_cases;

    for (int test = 1; test <= test_cases; test++){
        // cout << (solve() ? "YES" : "NO") << endl;
        solve();
    }

    cerr << "Time: " << int((double) (clock() - startTime) / CLOCKS_PER_SEC * 1000) << " ms" << endl;

    return 0;
}

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