oj.uz

Submission #503447

# Submission time Handle Problem Language Result Execution time Memory
503447 2022-01-08T02:39:50 Z Lobo One-Way Streets (CEOI17_oneway) C++17
100 / 100
 86 ms 19564 KB 
#include<bits/stdc++.h>
using namespace std;

const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 110000

int n, m, q;
int mark[maxn], span[maxn], h[maxn];
int low[maxn], ps[maxn];
vector<pair<int,int>> g[maxn];
pair<int,int> edg[maxn];
vector<int> roots;

void dfstree(int u, int idant, int ant) {
    mark[u] = 1;

    for(auto V : g[u]) {
        int v = V.fr;
        int id = V.sc;
        if(idant == id) continue;

        if(!mark[v]) {
            span[id] = 1;
            h[v] = h[u]+1;
            dfstree(v,id,u);
        }
    }
}

void dfslow(int u, int idant, int ant) {

    low[u] = inf;
    for(auto V : g[u]) {
        int v = V.fr;
        int id = V.sc;
        if(id == idant) continue;

        if(span[id]) {
            dfslow(v,id,u);
            low[u] = min(low[u],low[v]);
        }
        else {
            if(h[v] < h[u]) low[u] = min(low[u],h[v]);
        }

    }
}

void dfsps(int u, int ant) {

    for(auto V : g[u]) {
        int v = V.fr;
        int id = V.sc;
        if(v == ant || !span[id]) continue;

        dfsps(v,u);
        ps[u]+= ps[v];
    }
}

void solve() {
    cin >> n >> m;

    for(int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].pb(mp(v,i));
        g[v].pb(mp(u,i));
        edg[i] = mp(u,v);
    }

    for(int i = 1; i <= n; i++) {
        if(!mark[i]) {
            dfstree(i,0,i);
            roots.pb(i);
        }
    }

    for(auto x : roots) {
        dfslow(x,0,x);
    }

    cin >> q;
    for(int i = 1; i <= q; i++) {
        int u, v;
        cin >> u >> v;

        ps[u]++;
        ps[v]--;
    }

    for(auto x : roots) {
        dfsps(x,x);
    }

    for(int i = 1; i <= m; i++) {
        if(edg[i].fr == edg[i].sc) {
            cout << 'B';
            continue;
        }
        int ans = 1;

        int u = edg[i].fr;
        int v = edg[i].sc;

        if(h[u] > h[v]) {swap(u,v); ans*= -1;}

        //u e pai de v

        ans*= ps[v];
        if(low[v] <= h[u] || !span[i]) {
            cout << 'B';
        }
        else {
            if(ans > 0) cout << 'L';
            else if(ans < 0) cout << 'R';
            else cout << 'B';
        }
    }

    cout << endl;


}

//encontrar todas as bridge edges com dfs tree
//caminho u->lc->v -- prefix sum ps[u]++, ps[v]-- -> dsfps
// + = subindo, - = descendo

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

    // freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);

    int tt = 1;
    // cin >> tt;
    while(tt--) solve();
    return 0;

}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2892 KB Output is correct
2 Correct 2 ms 2896 KB Output is correct
3 Correct 2 ms 3012 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 2 ms 3020 KB Output is correct
6 Correct 2 ms 2916 KB Output is correct
7 Correct 2 ms 3020 KB Output is correct
8 Correct 2 ms 2916 KB Output is correct
9 Correct 2 ms 3020 KB Output is correct
10 Correct 2 ms 3020 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2892 KB Output is correct
2 Correct 2 ms 2896 KB Output is correct
3 Correct 2 ms 3012 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 2 ms 3020 KB Output is correct
6 Correct 2 ms 2916 KB Output is correct
7 Correct 2 ms 3020 KB Output is correct
8 Correct 2 ms 2916 KB Output is correct
9 Correct 2 ms 3020 KB Output is correct
10 Correct 2 ms 3020 KB Output is correct
11 Correct 39 ms 12988 KB Output is correct
12 Correct 57 ms 14044 KB Output is correct
13 Correct 69 ms 15068 KB Output is correct
14 Correct 70 ms 16232 KB Output is correct
15 Correct 85 ms 16580 KB Output is correct
16 Correct 73 ms 14696 KB Output is correct
17 Correct 61 ms 15964 KB Output is correct
18 Correct 61 ms 14708 KB Output is correct
19 Correct 54 ms 16940 KB Output is correct
20 Correct 54 ms 13764 KB Output is correct
21 Correct 44 ms 13416 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2892 KB Output is correct
2 Correct 2 ms 2896 KB Output is correct
3 Correct 2 ms 3012 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 2 ms 3020 KB Output is correct
6 Correct 2 ms 2916 KB Output is correct
7 Correct 2 ms 3020 KB Output is correct
8 Correct 2 ms 2916 KB Output is correct
9 Correct 2 ms 3020 KB Output is correct
10 Correct 2 ms 3020 KB Output is correct
11 Correct 39 ms 12988 KB Output is correct
12 Correct 57 ms 14044 KB Output is correct
13 Correct 69 ms 15068 KB Output is correct
14 Correct 70 ms 16232 KB Output is correct
15 Correct 85 ms 16580 KB Output is correct
16 Correct 73 ms 14696 KB Output is correct
17 Correct 61 ms 15964 KB Output is correct
18 Correct 61 ms 14708 KB Output is correct
19 Correct 54 ms 16940 KB Output is correct
20 Correct 54 ms 13764 KB Output is correct
21 Correct 44 ms 13416 KB Output is correct
22 Correct 70 ms 17120 KB Output is correct
23 Correct 86 ms 15904 KB Output is correct
24 Correct 81 ms 15940 KB Output is correct
25 Correct 67 ms 19564 KB Output is correct
26 Correct 82 ms 16752 KB Output is correct
27 Correct 81 ms 15880 KB Output is correct
28 Correct 30 ms 9892 KB Output is correct
29 Correct 66 ms 14556 KB Output is correct
30 Correct 68 ms 14696 KB Output is correct
31 Correct 73 ms 14900 KB Output is correct
32 Correct 60 ms 16708 KB Output is correct