oj.uz

Submission #667193

# Submission time Handle Problem Language Result Execution time Memory
667193 2022-11-30T16:56:13 Z keyurchd_11 One-Way Streets (CEOI17_oneway) C++14
100 / 100
 69 ms 17300 KB 
// Problem: https://oj.uz/problem/view/CEOI17_oneway
// #pragma GCC optimize("O3")
// #pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T>
using o_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)
#define int long long
typedef pair<int, int> II;
typedef vector<II> VII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long LL;
#define PB push_back
#define F first
#define S second
#define ALL(a) a.begin(), a.end()
#define SET(a, b) memset(a, b, sizeof(a))
#define SZ(a) (int)(a.size())
#define FOR(i, a, b) for (int i = (a); i < (int)(b); ++i)
#define fast_io                       \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL)
#define deb(a) cerr << #a << " = " << (a) << endl;
#define deb1(a)                                                        \
    cerr << #a << " = [ ";                                             \
    for (auto it = a.begin(); it != a.end(); it++) cerr << *it << " "; \
    cerr << "]\n";
#define endl "\n"
const long long mod = 1e9 + 7;

VVI g;
VI U, V, dep, up, bal;
string ans;
int other(int e, int u) { return U[e] ^ V[e] ^ u; }

void dfs(int u, int pe, int d) {
    up[u] = dep[u] = d;
    for (auto e : g[u]) {
        int v = other(e, u);
        if (e == pe) continue;
        if (dep[v] == 0) {
            dfs(v, e, d + 1);
            if (up[v] <= d || bal[v] == 0)
                ans[e] = 'B';
            else {
                ans[e] = 'R';
                if (bal[v] < 0 && U[e] != u)  // go towards v
                    ans[e] = 'L';
                else if (bal[v] > 0 && U[e] == u)  // come towards u
                    ans[e] = 'L';
            }
            bal[u] += bal[v];
        }
        up[u] = min(up[u], up[v]);
    }
}

void solve() {
    int n, m;
    cin >> n >> m;
    g = VVI(n, VI());
    U = V = VI(m);
    ans.assign(m, 'B');
    dep = up = bal = VI(n, 0);

    FOR(i, 0, m) {
        cin >> U[i] >> V[i];
        U[i]--, V[i]--;
        g[U[i]].PB(i), g[V[i]].PB(i);
    }
    int p;
    cin >> p;
    while (p--) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        bal[a]++;
        bal[b]--;
    }
    FOR(i, 0, n) {
        if (dep[i] == 0)
            dfs(i, -1, 1);
    }
    cout << ans << endl;
}

signed main() {
    fast_io;
    //  freopen("input.txt", "r", stdin);
    //  freopen("output.txt", "w", stdout);
    int totalTests = 1;
    // cin >> totalTests;
    for (int testNo = 1; testNo <= totalTests; testNo++) {
        // cout << "Case #" << testNo << ": ";
        solve();
    }
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 32 ms 7968 KB Output is correct
12 Correct 37 ms 9164 KB Output is correct
13 Correct 45 ms 10996 KB Output is correct
14 Correct 52 ms 12688 KB Output is correct
15 Correct 54 ms 13204 KB Output is correct
16 Correct 46 ms 11592 KB Output is correct
17 Correct 48 ms 13128 KB Output is correct
18 Correct 53 ms 11576 KB Output is correct
19 Correct 40 ms 14232 KB Output is correct
20 Correct 36 ms 9552 KB Output is correct
21 Correct 33 ms 9292 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 32 ms 7968 KB Output is correct
12 Correct 37 ms 9164 KB Output is correct
13 Correct 45 ms 10996 KB Output is correct
14 Correct 52 ms 12688 KB Output is correct
15 Correct 54 ms 13204 KB Output is correct
16 Correct 46 ms 11592 KB Output is correct
17 Correct 48 ms 13128 KB Output is correct
18 Correct 53 ms 11576 KB Output is correct
19 Correct 40 ms 14232 KB Output is correct
20 Correct 36 ms 9552 KB Output is correct
21 Correct 33 ms 9292 KB Output is correct
22 Correct 58 ms 14320 KB Output is correct
23 Correct 69 ms 12776 KB Output is correct
24 Correct 65 ms 12772 KB Output is correct
25 Correct 56 ms 17300 KB Output is correct
26 Correct 63 ms 13952 KB Output is correct
27 Correct 60 ms 12848 KB Output is correct
28 Correct 25 ms 5360 KB Output is correct
29 Correct 54 ms 10396 KB Output is correct
30 Correct 50 ms 10476 KB Output is correct
31 Correct 54 ms 10700 KB Output is correct
32 Correct 52 ms 13112 KB Output is correct