oj.uz

Submission #988493

# Submission time Handle Problem Language Result Execution time Memory
988493 2024-05-25T03:56:30 Z steveonalex One-Way Streets (CEOI17_oneway) C++17
100 / 100
 78 ms 24144 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
 
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ll mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}
 
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
 
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b) {a = b; return true;}
        return false;
    }
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b) {a = b; return true;}
        return false;
    }
 
template <class T>
    void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
        for(auto item: container) out << item << separator;
        out << finish;
    }
 
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

const int N = 1e5 + 69;
int n, m, p;
vector<int> graph[N];
int low[N], num[N], topo[N];
deque<int> st;
pair<int, int> edge[N];

void dfs(int u, int p){
    num[u] = low[u] = ++num[0];
    st.push_back(u);
    for(int v: graph[u]) {
        if (v == p){p = -1; continue;}
        if (!num[v]){
            dfs(v, u);
            minimize(low[u], low[v]);
        }
        else minimize(low[u], num[v]);
    }

    if (num[u] == low[u]){
        topo[0]++;
        while(st.back() != u){
            topo[st.back()] = topo[0];
            st.pop_back();
        }
        st.pop_back();
        topo[u] = topo[0];
    }
}

vector<pair<int, int>> bridge_tree[N];
pair<int, int> par[N];
int h[N];

void go(int u, int p){
    h[u] = h[p] + 1;
    for(pair<int, int> v: bridge_tree[u]) if (v.first != p){
        par[v.first] = {u, v.second};
        go(v.first, u);
    }
}

struct DSU{
    int n;
    vector<int> parent, sz, mi;

    DSU(int _n){
        n = _n;
        parent.resize(n+1); sz.resize(n+1, 1);
        for(int i = 1; i<=n; ++i) parent[i] = i;
        mi = parent;
    }

    int find_set(int u){return (u == parent[u]) ? u : (parent[u] = find_set(parent[u]));}
    bool same_set(int u, int v){return find_set(u) == find_set(v);}

    bool join_set(int u, int v){
        u = find_set(u), v = find_set(v);
        if (u != v){
            if (sz[u] < sz[v]) {swap(u, v); mi[u] = mi[v];}
            parent[v] = u;
            sz[u] += sz[v];
            return true;
        }
        return false;
    }

    int get_size(int u){return sz[find_set(u)];}

    int get_mi(int u){return mi[find_set(u)];}
};

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> m;
    for(int i = 0; i<m; ++i){
        int u, v; cin >> u >> v;
        edge[i] = {u, v};
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

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

    string ans(m, 'B');
    for(int i = 0; i<m; ++i){
        int u = edge[i].first, v = edge[i].second;
        u = topo[u], v = topo[v];
        if (u == v) continue;
        bridge_tree[u].push_back({v, i});
        bridge_tree[v].push_back({u, i});
    }

    for(int i = 1; i<=topo[0]; ++i) if (h[i] == 0) {
        go(i, 0);
    }

    cin >> p;

    DSU mst(topo[0]);
    for(int i = 0; i<p; ++i){
        int u, v; cin >> u >> v;
        u = topo[u], v = topo[v];
        u = mst.get_mi(u); v = mst.get_mi(v);
        while(u != v){
            if (h[u] > h[v]){
                ans[par[u].second] = 'R';
                mst.join_set(par[u].first, u);
                u = mst.get_mi(u);
            }
            else{
                ans[par[v].second] = 'L';
                mst.join_set(par[v].first, v);
                v = mst.get_mi(v);
            }
        }
    }

    for(int i= 0; i<m; ++i) if (ans[i] != 'B'){
        bool to_root = (ans[i] == 'R');
        int u = edge[i].first, v = edge[i].second;
        u = topo[u], v = topo[v];
        if ((h[u] > h[v]) == to_root) ans[i] = 'R';
        else ans[i] = 'L';
    }

    cout << ans << "\n";


    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8024 KB Output is correct
2 Correct 3 ms 8028 KB Output is correct
3 Correct 3 ms 8028 KB Output is correct
4 Correct 3 ms 8028 KB Output is correct
5 Correct 3 ms 8028 KB Output is correct
6 Correct 3 ms 8028 KB Output is correct
7 Correct 4 ms 8040 KB Output is correct
8 Correct 3 ms 8028 KB Output is correct
9 Correct 3 ms 8024 KB Output is correct
10 Correct 3 ms 8028 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8024 KB Output is correct
2 Correct 3 ms 8028 KB Output is correct
3 Correct 3 ms 8028 KB Output is correct
4 Correct 3 ms 8028 KB Output is correct
5 Correct 3 ms 8028 KB Output is correct
6 Correct 3 ms 8028 KB Output is correct
7 Correct 4 ms 8040 KB Output is correct
8 Correct 3 ms 8028 KB Output is correct
9 Correct 3 ms 8024 KB Output is correct
10 Correct 3 ms 8028 KB Output is correct
11 Correct 24 ms 12380 KB Output is correct
12 Correct 26 ms 13348 KB Output is correct
13 Correct 32 ms 14420 KB Output is correct
14 Correct 33 ms 15960 KB Output is correct
15 Correct 39 ms 16336 KB Output is correct
16 Correct 41 ms 17744 KB Output is correct
17 Correct 42 ms 19540 KB Output is correct
18 Correct 41 ms 17752 KB Output is correct
19 Correct 46 ms 20788 KB Output is correct
20 Correct 33 ms 12756 KB Output is correct
21 Correct 24 ms 12636 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8024 KB Output is correct
2 Correct 3 ms 8028 KB Output is correct
3 Correct 3 ms 8028 KB Output is correct
4 Correct 3 ms 8028 KB Output is correct
5 Correct 3 ms 8028 KB Output is correct
6 Correct 3 ms 8028 KB Output is correct
7 Correct 4 ms 8040 KB Output is correct
8 Correct 3 ms 8028 KB Output is correct
9 Correct 3 ms 8024 KB Output is correct
10 Correct 3 ms 8028 KB Output is correct
11 Correct 24 ms 12380 KB Output is correct
12 Correct 26 ms 13348 KB Output is correct
13 Correct 32 ms 14420 KB Output is correct
14 Correct 33 ms 15960 KB Output is correct
15 Correct 39 ms 16336 KB Output is correct
16 Correct 41 ms 17744 KB Output is correct
17 Correct 42 ms 19540 KB Output is correct
18 Correct 41 ms 17752 KB Output is correct
19 Correct 46 ms 20788 KB Output is correct
20 Correct 33 ms 12756 KB Output is correct
21 Correct 24 ms 12636 KB Output is correct
22 Correct 78 ms 20692 KB Output is correct
23 Correct 60 ms 18768 KB Output is correct
24 Correct 61 ms 18892 KB Output is correct
25 Correct 58 ms 24144 KB Output is correct
26 Correct 58 ms 20048 KB Output is correct
27 Correct 62 ms 18772 KB Output is correct
28 Correct 21 ms 10576 KB Output is correct
29 Correct 51 ms 13508 KB Output is correct
30 Correct 40 ms 13480 KB Output is correct
31 Correct 40 ms 14164 KB Output is correct
32 Correct 46 ms 17488 KB Output is correct