Submission #667192

#	Time	Username	Problem	Language	Result	Execution time	Memory
667192		keyurchd_11	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	0 ms	212 KiB

oneway

// 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: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40