oj.uz

Submission #715272

# Submission time Handle Problem Language Result Execution time Memory
715272 2023-03-26T10:19:08 Z dxz05 One-Way Streets (CEOI17_oneway) C++17
100 / 100
 345 ms 57236 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 20692 KB Output is correct
2 Correct 12 ms 20692 KB Output is correct
3 Correct 12 ms 20872 KB Output is correct
4 Correct 12 ms 20948 KB Output is correct
5 Correct 13 ms 21020 KB Output is correct
6 Correct 11 ms 20800 KB Output is correct
7 Correct 16 ms 20980 KB Output is correct
8 Correct 12 ms 21004 KB Output is correct
9 Correct 14 ms 20884 KB Output is correct
10 Correct 15 ms 20872 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 20692 KB Output is correct
2 Correct 12 ms 20692 KB Output is correct
3 Correct 12 ms 20872 KB Output is correct
4 Correct 12 ms 20948 KB Output is correct
5 Correct 13 ms 21020 KB Output is correct
6 Correct 11 ms 20800 KB Output is correct
7 Correct 16 ms 20980 KB Output is correct
8 Correct 12 ms 21004 KB Output is correct
9 Correct 14 ms 20884 KB Output is correct
10 Correct 15 ms 20872 KB Output is correct
11 Correct 110 ms 32924 KB Output is correct
12 Correct 118 ms 34052 KB Output is correct
13 Correct 115 ms 35488 KB Output is correct
14 Correct 156 ms 38488 KB Output is correct
15 Correct 136 ms 39764 KB Output is correct
16 Correct 160 ms 44744 KB Output is correct
17 Correct 222 ms 48448 KB Output is correct
18 Correct 176 ms 44832 KB Output is correct
19 Correct 180 ms 49852 KB Output is correct
20 Correct 104 ms 33744 KB Output is correct
21 Correct 93 ms 33332 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 20692 KB Output is correct
2 Correct 12 ms 20692 KB Output is correct
3 Correct 12 ms 20872 KB Output is correct
4 Correct 12 ms 20948 KB Output is correct
5 Correct 13 ms 21020 KB Output is correct
6 Correct 11 ms 20800 KB Output is correct
7 Correct 16 ms 20980 KB Output is correct
8 Correct 12 ms 21004 KB Output is correct
9 Correct 14 ms 20884 KB Output is correct
10 Correct 15 ms 20872 KB Output is correct
11 Correct 110 ms 32924 KB Output is correct
12 Correct 118 ms 34052 KB Output is correct
13 Correct 115 ms 35488 KB Output is correct
14 Correct 156 ms 38488 KB Output is correct
15 Correct 136 ms 39764 KB Output is correct
16 Correct 160 ms 44744 KB Output is correct
17 Correct 222 ms 48448 KB Output is correct
18 Correct 176 ms 44832 KB Output is correct
19 Correct 180 ms 49852 KB Output is correct
20 Correct 104 ms 33744 KB Output is correct
21 Correct 93 ms 33332 KB Output is correct
22 Correct 311 ms 53072 KB Output is correct
23 Correct 283 ms 51144 KB Output is correct
24 Correct 310 ms 51104 KB Output is correct
25 Correct 306 ms 57236 KB Output is correct
26 Correct 299 ms 52844 KB Output is correct
27 Correct 345 ms 51408 KB Output is correct
28 Correct 60 ms 24952 KB Output is correct
29 Correct 125 ms 35216 KB Output is correct
30 Correct 123 ms 35264 KB Output is correct
31 Correct 120 ms 35224 KB Output is correct
32 Correct 178 ms 40808 KB Output is correct