oj.uz

Submission #910051

# Submission time Handle Problem Language Result Execution time Memory
910051 2024-01-17T20:08:53 Z Denisov One-Way Streets (CEOI17_oneway) C++14
100 / 100
 148 ms 32216 KB 
//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#include <bits/stdc++.h>

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef KIVI
#define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define DEBUG while (false)
#define LOG(...)
#endif

const int max_n = 1e5 + 11, inf = 1000111222;


struct ed {
    int to, id;
};

vector <ed> edge[max_n], g[max_n];

int used[max_n], bridge[max_n], tin[max_n], timer = 1, low[max_n];

inline void dfs (int v, int p = -1) {
    used[v] = 1;
    tin[v] = low[v] = timer++;
    for (auto &e : edge[v]) {
        int to = e.to, id = e.id;
        if (id == p) {
            continue;
        }
        if (used[to]) {
            umin(low[v], tin[to]);
        }
        else {
            dfs(to, id);
            umin(low[v], low[to]);
            if (low[to] > tin[v]) {
                bridge[id] = 1;
            }
        }
    }
}

int cmp[max_n];

inline void color (int v, int c) {
    used[v] = 2;
    cmp[v] = c;
    for (auto &e : edge[v]) {
        int to = e.to, id = e.id;
        if (used[to] == 1 && !bridge[id]) {
            color(to, c);
        }
    }
}


int up[max_n], down[max_n];

int res[max_n], d[max_n];


inline void go (int v, int p = -1) {
    used[v] = 4;
    for (auto &i : g[v]) {
        int to = i.to, id = i.id;
        if (to == p) {
            continue;
        }
        d[to] = d[v] + 1;
        go(to, v);
        if (up[to]) {
            res[id] = 1;
        }
        if (down[to]) {
            res[id] = 2;
        }
        up[v] += up[to];
        down[v] += down[to];
    }
}


int L = 0, T = 0;
vector <int> upp[max_n];
int tin1[max_n], tout[max_n];

inline void dfs_lca (int v, int p = -1) {
    tin1[v] = T++;
    used[v] = 3;
    upp[v].resize(L + 1);
    upp[v][0] = p == -1 ? v : p;
    for (int i = 1; i <= L; i++) {
        upp[v][i] = upp[upp[v][i - 1]][i - 1];
    }
    for (auto &i : g[v]) {
        int to = i.to;
        if (to == p) continue;
        dfs_lca(to, v);
    }
    tout[v] = T;
}

inline bool upper (int a, int b) {
    return tin1[a] <= tin1[b] && tout[b] <= tout[a];
}

inline int lca (int a, int b) {
    if (upper(a, b)) return a;
    if (upper(b, a)) return b;
    for (int i = L; i >= 0; i--) {
        if (!upper(upp[a][i], b)) {
            a = upp[a][i];
        }
    }
    return upp[a][0];
}


int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m, p;
    cin >> n >> m;
    while ((1 << L) <= n) ++L;
    vector <pii> e(m);
    for (int i = 0, a, b; i < m; i++) {
        cin >> a >> b;
        --a, --b;
        e[i] = {a, b};
        edge[a].pb({b, i});
        edge[b].pb({a, i});
    }
    cin >> p;


    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            dfs(i);
        }
    }

    int num = 0;
    for (int i = 0; i < n; i++) {
        if (used[i] == 1) {
            color(i, num);
            ++num;
        }
    }

    for (int i = 0, j = 0; i < m; i++) {
        int a = cmp[e[i].first];
        int b = cmp[e[i].second];
        if (a != b) {
            g[a].pb({b, j});
            g[b].pb({a, j});
            ++j;
        }
    }

    for (int i = 0; i < num; i++) {
        if (used[i] == 2) {
            dfs_lca(i);
        }
    }

    for (int i = 0, a, b; i < p; i++) {
        cin >> a >> b;
        --a, --b;
        a = cmp[a];
        b = cmp[b];
        if (a == b) {
            continue;
        }
        int v = lca(a, b);
        down[a] += 1;
        down[v] -= 1;

        up[b] += 1;
        up[v] -= 1;
    }

    for (int i = 0; i < num; i++) {
        if (used[i] == 3) {
            go(i);
        }
    }

    for (int i = 0, j = 0; i < m; i++) {
        int a = cmp[e[i].first];
        int b = cmp[e[i].second];
        if (a != b) {
            if (res[j] == 0) {
                cout << 'B';
            }
            else if (res[j] == 1) {
                if (d[a] < d[b]) {
                    cout << 'R';
                }
                else {
                    cout << 'L';
                }
            }
            else {
                if (d[a] < d[b]) {
                    cout << 'L';
                }
                else {
                    cout << 'R';
                }
            }
            ++j;
        }
        else {
            cout << 'B';
        }
    }
    cout << '\n';
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9816 KB Output is correct
2 Correct 3 ms 9560 KB Output is correct
3 Correct 3 ms 9816 KB Output is correct
4 Correct 4 ms 9564 KB Output is correct
5 Correct 3 ms 9564 KB Output is correct
6 Correct 3 ms 9564 KB Output is correct
7 Correct 4 ms 9564 KB Output is correct
8 Correct 3 ms 9564 KB Output is correct
9 Correct 4 ms 9564 KB Output is correct
10 Correct 3 ms 9560 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9816 KB Output is correct
2 Correct 3 ms 9560 KB Output is correct
3 Correct 3 ms 9816 KB Output is correct
4 Correct 4 ms 9564 KB Output is correct
5 Correct 3 ms 9564 KB Output is correct
6 Correct 3 ms 9564 KB Output is correct
7 Correct 4 ms 9564 KB Output is correct
8 Correct 3 ms 9564 KB Output is correct
9 Correct 4 ms 9564 KB Output is correct
10 Correct 3 ms 9560 KB Output is correct
11 Correct 27 ms 14940 KB Output is correct
12 Correct 37 ms 15956 KB Output is correct
13 Correct 37 ms 16976 KB Output is correct
14 Correct 49 ms 20308 KB Output is correct
15 Correct 55 ms 21612 KB Output is correct
16 Correct 81 ms 29008 KB Output is correct
17 Correct 105 ms 29400 KB Output is correct
18 Correct 84 ms 28912 KB Output is correct
19 Correct 94 ms 29932 KB Output is correct
20 Correct 31 ms 15452 KB Output is correct
21 Correct 35 ms 15952 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9816 KB Output is correct
2 Correct 3 ms 9560 KB Output is correct
3 Correct 3 ms 9816 KB Output is correct
4 Correct 4 ms 9564 KB Output is correct
5 Correct 3 ms 9564 KB Output is correct
6 Correct 3 ms 9564 KB Output is correct
7 Correct 4 ms 9564 KB Output is correct
8 Correct 3 ms 9564 KB Output is correct
9 Correct 4 ms 9564 KB Output is correct
10 Correct 3 ms 9560 KB Output is correct
11 Correct 27 ms 14940 KB Output is correct
12 Correct 37 ms 15956 KB Output is correct
13 Correct 37 ms 16976 KB Output is correct
14 Correct 49 ms 20308 KB Output is correct
15 Correct 55 ms 21612 KB Output is correct
16 Correct 81 ms 29008 KB Output is correct
17 Correct 105 ms 29400 KB Output is correct
18 Correct 84 ms 28912 KB Output is correct
19 Correct 94 ms 29932 KB Output is correct
20 Correct 31 ms 15452 KB Output is correct
21 Correct 35 ms 15952 KB Output is correct
22 Correct 139 ms 30644 KB Output is correct
23 Correct 123 ms 29972 KB Output is correct
24 Correct 127 ms 30256 KB Output is correct
25 Correct 148 ms 32216 KB Output is correct
26 Correct 123 ms 30592 KB Output is correct
27 Correct 121 ms 29932 KB Output is correct
28 Correct 27 ms 13648 KB Output is correct
29 Correct 44 ms 16460 KB Output is correct
30 Correct 45 ms 16764 KB Output is correct
31 Correct 46 ms 16468 KB Output is correct
32 Correct 63 ms 21328 KB Output is correct