oj.uz

Submission #696206

# Submission time Handle Problem Language Result Execution time Memory
696206 2023-02-05T21:25:20 Z hamidh100 One-Way Streets (CEOI17_oneway) C++17
100 / 100
 182 ms 28696 KB 
/* In the name of God */

#include <iostream>
#include <iomanip>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <bitset>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <list>
#include <map>
#include <numeric>
#include <limits>
#include <limits.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef map<int, int> MPII;
typedef vector<int> VI;
typedef vector<ll> VL;
#define PB push_back
#define POP pop_back
#define MP make_pair
#define all(a) (a).begin(), (a).end()
#define SORT(a) sort(all(a))
#define REVERSE(a) reverse(all(a))
#define sep ' '
#define endl '\n'
#define dbg(x) cerr << '[' << #x << ": " << x << "]\n"
#define dbg2(x, y) cerr << '[' << #x << ": " << x << ", " << #y << ": " << y << "]\n"
#define Yes cout << "Yes\n"
#define YES cout << "YES\n"
#define No cout << "No\n"
#define NO cout << "NO\n"
#define OK cout << "OK\n"

const ll INF = (ll)2e18 + 1386;
const ld eps = 0.000000000000001;
const int MOD = 1e9 + 7;

inline int mod_add(int a, int b){ int res = a + b; return (res >= MOD? res - MOD : res); }
inline int mod_neg(int a, int b){ int res = (abs(a - b) < MOD? a - b : (a - b) % MOD); return (res < 0? res + MOD : res); }
inline int mod_mlt(int a, int b){ return (1ll * a * b % MOD); }
inline string intToString(ll a){ char x[100]; sprintf(x, "%lld", a); string s = x; return s; }
inline ll stringToInt(string s){ ll res; char x[100]; strcpy(x, s.c_str()); sscanf(x, "%lld", &res); return res; }
inline void fileIO(string i, string o){ freopen(i.c_str(), "r", stdin); freopen(o.c_str(), "w", stdout); }

const int MAXN = 2e5 + 5, LOG = 23;

int n, m, q, par[MAXN][LOG], h[MAXN], psU[MAXN], psD[MAXN], st[MAXN], mnback[MAXN], timer, ans[MAXN], jahat[MAXN];
bool boreshi[MAXN], mark[MAXN], mark2[MAXN];
vector<PII> N[MAXN];

void dfs(int v, int lst, int height){
    mark[v] = 1;
    h[v] = height++;
    mnback[v] = st[v] = timer++;
    for (auto [u, e] : N[v]){
        if (!mark[u]){
            par[u][0] = v;
            for (int i = 1; i < LOG; i++){
                par[u][i] = par[par[u][i - 1]][i - 1];
            }
            dfs(u, e, height);
            if (mnback[u] > st[v]) boreshi[e] = 1;
            mnback[v] = min(mnback[v], mnback[u]);
        }
        else if (e != lst){
            mnback[v] = min(mnback[v], st[u]);
        }
    }
}

int balaaaaaa(int v, int k){
    for (int i = LOG - 1; i >= 0; i--){
        if (k >> i & 1){
            v = par[v][i];
        }
    }
    return v;
}

int LCA(int u, int v){
    if (h[u] > h[v]) swap(u, v);
    v = balaaaaaa(v, h[v] - h[u]);
    if (u == v) return v;
    for (int i = LOG - 1; i >= 0; i--){
        if (par[v][i] != par[u][i]){
            v = par[v][i], u = par[u][i];
        }
    }
    return par[u][0];
}

void dfs_ans(int v){
    mark2[v] = 1;
    for (auto [u, e] : N[v]){
        if (!mark2[u]){
            dfs_ans(u);
            psD[v] += psD[u], psU[v] += psU[u];
            if (boreshi[e] && (psD[u] || psU[u])){
                if ((jahat[e] == v && psD[u]) || (jahat[e] == u && psU[u])) ans[e] = 1;
                else ans[e] = 2;
            }
            else ans[e] = 3;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        int x, y; cin >> x >> y;
        N[x].PB({y, i}), N[y].PB({x, i});
        jahat[i] = x;
    }
    
    for (int i = 1; i <= n; i++){
        if (!mark2[i]){
            dfs_ans(i);
            for (int j = 0; j < LOG; j++){
                par[i][j] = i;
            }
            dfs(i, -1, 1);
        }
    }

    cin >> q;
    while (q--){
        int u, v; cin >> u >> v;
        int lca = LCA(u, v);
        psU[u]++, psU[lca]--;
        psD[v]++, psD[lca]--;
    }

    fill(mark2, mark2 + MAXN, 0);
    for (int i = 1; i <= n; i++){
        if (!mark2[i]){
            dfs_ans(i);
        }
    }

    for (int i = 1; i <= m; i++){
        if (ans[i] == 1) cout << 'R';
        else if (ans[i] == 2) cout << 'L';
        else cout << 'B';
    }
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 2 ms 5204 KB Output is correct
3 Correct 3 ms 5332 KB Output is correct
4 Correct 3 ms 5412 KB Output is correct
5 Correct 3 ms 5460 KB Output is correct
6 Correct 3 ms 5336 KB Output is correct
7 Correct 3 ms 5416 KB Output is correct
8 Correct 3 ms 5332 KB Output is correct
9 Correct 3 ms 5332 KB Output is correct
10 Correct 3 ms 5332 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 2 ms 5204 KB Output is correct
3 Correct 3 ms 5332 KB Output is correct
4 Correct 3 ms 5412 KB Output is correct
5 Correct 3 ms 5460 KB Output is correct
6 Correct 3 ms 5336 KB Output is correct
7 Correct 3 ms 5416 KB Output is correct
8 Correct 3 ms 5332 KB Output is correct
9 Correct 3 ms 5332 KB Output is correct
10 Correct 3 ms 5332 KB Output is correct
11 Correct 42 ms 13360 KB Output is correct
12 Correct 49 ms 15680 KB Output is correct
13 Correct 67 ms 18840 KB Output is correct
14 Correct 94 ms 22384 KB Output is correct
15 Correct 104 ms 23380 KB Output is correct
16 Correct 81 ms 22184 KB Output is correct
17 Correct 107 ms 24044 KB Output is correct
18 Correct 93 ms 22132 KB Output is correct
19 Correct 89 ms 25304 KB Output is correct
20 Correct 65 ms 17036 KB Output is correct
21 Correct 58 ms 16816 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 2 ms 5204 KB Output is correct
3 Correct 3 ms 5332 KB Output is correct
4 Correct 3 ms 5412 KB Output is correct
5 Correct 3 ms 5460 KB Output is correct
6 Correct 3 ms 5336 KB Output is correct
7 Correct 3 ms 5416 KB Output is correct
8 Correct 3 ms 5332 KB Output is correct
9 Correct 3 ms 5332 KB Output is correct
10 Correct 3 ms 5332 KB Output is correct
11 Correct 42 ms 13360 KB Output is correct
12 Correct 49 ms 15680 KB Output is correct
13 Correct 67 ms 18840 KB Output is correct
14 Correct 94 ms 22384 KB Output is correct
15 Correct 104 ms 23380 KB Output is correct
16 Correct 81 ms 22184 KB Output is correct
17 Correct 107 ms 24044 KB Output is correct
18 Correct 93 ms 22132 KB Output is correct
19 Correct 89 ms 25304 KB Output is correct
20 Correct 65 ms 17036 KB Output is correct
21 Correct 58 ms 16816 KB Output is correct
22 Correct 182 ms 25128 KB Output is correct
23 Correct 138 ms 23208 KB Output is correct
24 Correct 142 ms 23304 KB Output is correct
25 Correct 169 ms 28696 KB Output is correct
26 Correct 158 ms 24632 KB Output is correct
27 Correct 128 ms 23280 KB Output is correct
28 Correct 34 ms 8944 KB Output is correct
29 Correct 95 ms 17700 KB Output is correct
30 Correct 104 ms 17956 KB Output is correct
31 Correct 98 ms 18200 KB Output is correct
32 Correct 106 ms 21940 KB Output is correct