oj.uz

Submission #886237

# Submission time Handle Problem Language Result Execution time Memory
886237 2023-12-11T15:33:28 Z dwuy One-Way Streets (CEOI17_oneway) C++14
100 / 100
 113 ms 22444 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
const int INF = 1e9;

struct SMT{
    int n;
    vector<pii> tree; /// {Min, Max}

    SMT(int n=0){
        this->n = n;
        this->tree.assign(n<<2|1, {INF, -INF});
    }

    pii combine(pii a, pii b){
        return {min(a.fi, b.fi), max(a.se, b.se)};
    }

    void update(int pos, int val){
        int l = 1, r = n, id = 1;
        while(l<r){
            int mid = (l+r)>>1;
            if(pos<=mid) id <<= 1, r = mid;
            else l = mid + 1, id = id<<1|1;
        }
        if(val>=tree[id].fi && val<=tree[id].se) return;
        tree[id] = combine(tree[id], {val, val});
        for(id>>=1; id; id>>=1) tree[id] = combine(tree[id<<1], tree[id<<1|1]);
    }

    pii get(int l, int r, int id, const int &u, const int &v){
        if(l>v || r<u) return tree[0];
        if(l>=u && r<=v) return tree[id];
        int mid = (l+r)>>1;
        return combine(get(l, mid, id<<1, u, v), get(mid+1, r, id<<1|1, u, v));
    }

    pii get(int u, int v){
        return get(1, n, 1, u, v);
    }
};

struct DSU{
    int n;
    vector<int> e;

    DSU(int n=0){
        this->n = n;
        this->e.assign(n+5, -1);
    }

    int fp(int u){
        return e[u]<0? u : e[u] = fp(e[u]);
    }

    void unon(int u, int v){
        u = fp(u);
        v = fp(v);
        if(u==v) return;
        if(e[u] > e[v]) swap(u, v);
        e[u] += e[v];
        e[v] = u;
    }
};

const int MX = 100005;
int n, m, k, cnt = 0;
int num[MX]; /// open
int clo[MX]; /// close
int low[MX]; ///
bitset<MX> vist; /// visited edge
bitset<MX> isB; /// is bridge
pii edges[MX]; /// edges {u, v}
pii query[MX]; /// query {u, v}
vector<int> G[MX]; /// graph

void nhap(){
    cin >> n >> m;
    for(int i=1; i<=m; i++){
        int u, v;
        cin >> u >> v;
        edges[i] = {u, v};
        G[u].push_back(i);
        G[v].push_back(i);
    }
    cin >> k;
    for(int i=1; i<=k; i++){
        int u, v;
        cin >> u >> v;
        query[i] = {u, v};
    }
}

void tarjan(int u){
    num[u] = low[u] = ++cnt;
    for(int i: G[u]){
        if(vist[i]) continue;
        vist[i] = 1;
        int v = edges[i].fi^edges[i].se^u;
        if(num[v]) low[u] = min(low[u], num[v]);
        else{
            tarjan(v);
            low[u] = min(low[u], low[v]);
            if(low[v]>num[u]) isB[i] = 1;
        }
    }
    clo[u] = cnt;
}


void solve(){
    vist = 0;
    for(int i=1; i<=n; i++) if(!num[i]) tarjan(i);
    SMT smt(n), rsmt(n);
    for(int i=1; i<=k; i++){
        int u, v;
        tie(u, v) = query[i];
        smt.update(num[u], num[v]);
        rsmt.update(num[v], num[u]);
    }
    string ans = "";
    for(int i=1; i<=m; i++){
        int u, v;
        tie(u, v) = edges[i];
        if(!isB[i]){
            ans += 'B';
            continue;
        }
        bool flag = 0;
        if(num[u] > num[v]) swap(u, v), flag = 1;
        pii r1 = smt.get(num[v], clo[v]);
        pii r2 = rsmt.get(num[v], clo[v]);
        assert(!((r1.fi < num[v] || r1.se > clo[v]) && (r2.fi < num[v] || r2.se > clo[v])));
        if(r2.fi < num[v] || r2.se > clo[v]) ans += flag? 'L':'R';
        else if(r1.fi < num[v] || r1.se > clo[v]) ans += flag? 'R':'L';
        else ans += 'B';
    }
    cout << ans;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    nhap();
    solve();

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 1 ms 4908 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 2 ms 4700 KB Output is correct
8 Correct 2 ms 4700 KB Output is correct
9 Correct 1 ms 4700 KB Output is correct
10 Correct 1 ms 4780 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 1 ms 4908 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 2 ms 4700 KB Output is correct
8 Correct 2 ms 4700 KB Output is correct
9 Correct 1 ms 4700 KB Output is correct
10 Correct 1 ms 4780 KB Output is correct
11 Correct 23 ms 10068 KB Output is correct
12 Correct 27 ms 12100 KB Output is correct
13 Correct 30 ms 14208 KB Output is correct
14 Correct 40 ms 16724 KB Output is correct
15 Correct 44 ms 17388 KB Output is correct
16 Correct 71 ms 16436 KB Output is correct
17 Correct 68 ms 18180 KB Output is correct
18 Correct 68 ms 16164 KB Output is correct
19 Correct 64 ms 19264 KB Output is correct
20 Correct 26 ms 12636 KB Output is correct
21 Correct 30 ms 12496 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 1 ms 4908 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 2 ms 4700 KB Output is correct
8 Correct 2 ms 4700 KB Output is correct
9 Correct 1 ms 4700 KB Output is correct
10 Correct 1 ms 4780 KB Output is correct
11 Correct 23 ms 10068 KB Output is correct
12 Correct 27 ms 12100 KB Output is correct
13 Correct 30 ms 14208 KB Output is correct
14 Correct 40 ms 16724 KB Output is correct
15 Correct 44 ms 17388 KB Output is correct
16 Correct 71 ms 16436 KB Output is correct
17 Correct 68 ms 18180 KB Output is correct
18 Correct 68 ms 16164 KB Output is correct
19 Correct 64 ms 19264 KB Output is correct
20 Correct 26 ms 12636 KB Output is correct
21 Correct 30 ms 12496 KB Output is correct
22 Correct 97 ms 18404 KB Output is correct
23 Correct 113 ms 16468 KB Output is correct
24 Correct 98 ms 16616 KB Output is correct
25 Correct 103 ms 22444 KB Output is correct
26 Correct 93 ms 18004 KB Output is correct
27 Correct 94 ms 16580 KB Output is correct
28 Correct 26 ms 6740 KB Output is correct
29 Correct 60 ms 12628 KB Output is correct
30 Correct 64 ms 13012 KB Output is correct
31 Correct 66 ms 13328 KB Output is correct
32 Correct 72 ms 16468 KB Output is correct