oj.uz

Submission #563714

# Submission time Handle Problem Language Result Execution time Memory
563714 2022-05-18T03:41:22 Z generic_placeholder_name One-Way Streets (CEOI17_oneway) C++17
100 / 100
 196 ms 33868 KB 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma,popcnt")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/rope>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define gcd __gcd
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define rep(i, n) for (int i=0; i<(n); i++)
#define rep1(i, n) for (int i=1; i<=(n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define endl "\n"

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned uint;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
template<typename T, typename cmp = less<T>>
using ordered_set = tree<T, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> pref_trie;

constexpr int N = 1e5 + 5;
vi adj[N], g[N];
int l[N], r[N];
int ans[N];
int x[N], y[N];
bool is_bridge[N];

int disc[N], low[N];
void dfs(int u, int idp = -1) {
    static int t = 0;
    disc[u] = low[u] = ++t;
    for(int id: adj[u]) if(id != idp) {
        int v = l[id] + r[id] - u;
        if(disc[v]) low[u] = min(low[u], disc[v]);
        else {
            dfs(v, id);
            low[u] = min(low[u], low[v]);
            if(low[v] > disc[u]) is_bridge[id] = 1;
        }
    }
}

int d[N];
int grp[N];
int find(int x) {return d[x] < 0 ? x : d[x] = find(d[x]);}
void join(int x, int y) {
    x = find(x), y = find(y);
    if(x == y) return;
    if(d[x] > d[y]) swap(x, y);
    d[x] += d[y]; d[y] = x;
}

constexpr int L = 17;
int pedge[N];
int par[N][L], lz[N][L];
int dep[N];

void dfs2(int u, int p) {
    rep1(i, L - 1) par[u][i] = par[par[u][i - 1]][i - 1];
    for(int id: g[u]) {
        int v = l[id] + r[id] - u;
        if(v != p) {
            pedge[v] = id;
            dep[v] = dep[u] + 1;
            par[v][0] = u;
            dfs2(v, u);
        }
    }
}

int lca(int u, int v) {
    if(dep[u] > dep[v]) swap(u, v);
    for(int i = L - 1; ~i; i--) if(dep[v] - (1 << i) >= dep[u]) {
        v = par[v][i];
    }
    if(u == v) return u;
    for(int i = L - 1; ~i; i--) if(par[u][i] != par[v][i]) {
        u = par[u][i];
        v = par[v][i];
    }
    return par[u][0];
}

void upd(int u, int v, int x) {
    for(int i = L - 1; ~i; i--) if(dep[u] - (1 << i) >= dep[v]) {
        lz[u][i] = x;
        u = par[u][i];
    }
}

int32_t main() {
    fastio;
    int n, m; cin >> n >> m;
    rep(i, m) {
        cin >> l[i] >> r[i]; --l[i], --r[i];
        adj[r[i]].pb(i);
        adj[l[i]].pb(i);
    }
    rep(i, n) if(!disc[i]) dfs(i);
    memset(d, -1, sizeof(d));
    memset(ans, -1, sizeof(ans));
    rep(i, m) if(!is_bridge[i]) join(l[i], r[i]);
    memset(grp, -1, sizeof(grp));
    int k = 0;
    rep(i, n) {
        int r = find(i);
        if(!~grp[r]) grp[r] = k++;
        grp[i] = grp[r];
    }
    rep(i, m) if(is_bridge[i]) {
        l[i] = grp[l[i]];
        r[i] = grp[r[i]];
        g[l[i]].pb(i);
        g[r[i]].pb(i);
    }
    memset(pedge, -1, sizeof(pedge));
    memset(par, -1, sizeof(par));
    memset(lz, -1, sizeof(lz));
    rep(i, k) if(!~par[i][0]) dfs2(i, i);
    int p; cin >> p;
    while(p--) {
        int x, y; cin >> x >> y; --x, --y;
        x = grp[x], y = grp[y];
        if(x == y) continue;
        int v = lca(x, y);
        upd(x, v, 1);
        upd(y, v, 0);
    }
    for(int i = L - 1; i; i--) {
        rep(u, k) if(~lz[u][i]) {
            lz[u][i - 1] = lz[u][i];
            lz[par[u][i - 1]][i - 1] = lz[u][i];
        }
    }
    rep(i, k) {
        int id = pedge[i];
        if(~lz[i][0]) {
            assert(id != -1);
            ans[id] = lz[i][0] ^ (i == l[id]);
        }
    }
    rep(i, m) cout << (!~ans[i] ? 'B' : ans[i] ? 'L' : 'R');
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19796 KB Output is correct
2 Correct 9 ms 19924 KB Output is correct
3 Correct 10 ms 19924 KB Output is correct
4 Correct 9 ms 19948 KB Output is correct
5 Correct 9 ms 19924 KB Output is correct
6 Correct 9 ms 19924 KB Output is correct
7 Correct 10 ms 19924 KB Output is correct
8 Correct 9 ms 19932 KB Output is correct
9 Correct 10 ms 19848 KB Output is correct
10 Correct 10 ms 19924 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19796 KB Output is correct
2 Correct 9 ms 19924 KB Output is correct
3 Correct 10 ms 19924 KB Output is correct
4 Correct 9 ms 19948 KB Output is correct
5 Correct 9 ms 19924 KB Output is correct
6 Correct 9 ms 19924 KB Output is correct
7 Correct 10 ms 19924 KB Output is correct
8 Correct 9 ms 19932 KB Output is correct
9 Correct 10 ms 19848 KB Output is correct
10 Correct 10 ms 19924 KB Output is correct
11 Correct 42 ms 24012 KB Output is correct
12 Correct 44 ms 25064 KB Output is correct
13 Correct 55 ms 26124 KB Output is correct
14 Correct 60 ms 27640 KB Output is correct
15 Correct 67 ms 27952 KB Output is correct
16 Correct 96 ms 28428 KB Output is correct
17 Correct 101 ms 30408 KB Output is correct
18 Correct 97 ms 28520 KB Output is correct
19 Correct 102 ms 31720 KB Output is correct
20 Correct 47 ms 24644 KB Output is correct
21 Correct 42 ms 24320 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19796 KB Output is correct
2 Correct 9 ms 19924 KB Output is correct
3 Correct 10 ms 19924 KB Output is correct
4 Correct 9 ms 19948 KB Output is correct
5 Correct 9 ms 19924 KB Output is correct
6 Correct 9 ms 19924 KB Output is correct
7 Correct 10 ms 19924 KB Output is correct
8 Correct 9 ms 19932 KB Output is correct
9 Correct 10 ms 19848 KB Output is correct
10 Correct 10 ms 19924 KB Output is correct
11 Correct 42 ms 24012 KB Output is correct
12 Correct 44 ms 25064 KB Output is correct
13 Correct 55 ms 26124 KB Output is correct
14 Correct 60 ms 27640 KB Output is correct
15 Correct 67 ms 27952 KB Output is correct
16 Correct 96 ms 28428 KB Output is correct
17 Correct 101 ms 30408 KB Output is correct
18 Correct 97 ms 28520 KB Output is correct
19 Correct 102 ms 31720 KB Output is correct
20 Correct 47 ms 24644 KB Output is correct
21 Correct 42 ms 24320 KB Output is correct
22 Correct 196 ms 30284 KB Output is correct
23 Correct 169 ms 28356 KB Output is correct
24 Correct 147 ms 28420 KB Output is correct
25 Correct 187 ms 33868 KB Output is correct
26 Correct 180 ms 29800 KB Output is correct
27 Correct 150 ms 28536 KB Output is correct
28 Correct 34 ms 21836 KB Output is correct
29 Correct 63 ms 24092 KB Output is correct
30 Correct 66 ms 24308 KB Output is correct
31 Correct 60 ms 24620 KB Output is correct
32 Correct 106 ms 28160 KB Output is correct