oj.uz

Submission #321778

# Submission time Handle Problem Language Result Execution time Memory
321778 2020-11-13T11:02:48 Z Karen124 One-Way Streets (CEOI17_oneway) C++14
100 / 100
 212 ms 17956 KB 
#include <bits/stdc++.h>
     
using namespace std;
     
#define ll long long int 
#define F first
#define S second
#define pb push_back
 
const ll N = 1e5 + 10;
const ll LOG = 20;
const ll MOD = 1e9 + 7;
const ll INF = 1e9 + 10;
struct Edge{
    int u, v;
} e[N];
int n, m, p, a[N], b[N];
int h[N], mn[N];
int pr[N], sz[N];
int rev[N], ps[N];
vector < pair <int, int> > adj[N];
vector <int>  E;
bool mrk[N], is[N];
void dfs(int v, int i){
    mrk[v] = 1; mn[v] = h[v];
    for (auto it : adj[v]){
        int u = it.F, j = it.S;
        if (!mrk[u]){
            h[u] = h[v] + 1;
            dfs(u, j);
            mn[v] = min(mn[u], mn[v]);
        }
        else if (i != j){
            mn[v] = min(mn[v], h[u]);   
        }
    }
    if(i && mn[v] == h[v]){
        E.pb(i);
        is[i] = 1;
    }
    return;
}
int find(int v){
    if (pr[v] == v) return v;
    return (pr[v] = find(pr[v]));
}
void merge(int u, int v){
    u = find(u); v = find(v);
    if (u == v) return;
    if (sz[v] < sz[u]) swap(u, v);
    pr[u] = v;
    sz[v] += sz[u];
    return;
}
void dfs_dead(int v, int i){
    mrk[v] = 1;
    for (auto it : adj[v]){
        int u = it.F, j = it.S;
        if (mrk[u]) continue;
        dfs_dead(u, j);
        ps[v] += ps[u];
    }
    if (i && ps[v]){
        rev[i] = 1;
        rev[i] += (0 < ps[v] && find(e[i].u) == v);    
        rev[i] += (ps[v] < 0 && find(e[i].v) == v);
    }
    return;
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        cin >> e[i].u >> e[i].v;
        adj[e[i].u].pb({e[i].v, i});
        adj[e[i].v].pb({e[i].u, i});
    }
    for (int i = 1; i <= n; i++){
        if (!mrk[i]){
            dfs(i, 0);
        }
        sz[i] = 1; pr[i] = i;
    }
    cin >> p;
    for (int i = 1; i <= p; i++){
        cin >> a[i] >> b[i];
    }
    for (int i = 1; i <= m; i++){
        if (!is[i]){
            merge(e[i].u, e[i].v);
        }
    }
    for (int i = 1; i <= n; i++) adj[i].clear();
    for (int i : E){
        adj[find(e[i].u)].pb({find(e[i].v), i});
        adj[find(e[i].v)].pb({find(e[i].u), i});
    }
    for (int i = 1; i <= p; i++){
        if (find(a[i]) == find(b[i])) continue;
        ps[find(a[i])]--; ps[find(b[i])]++; 
    }
    fill(mrk, mrk + n + 1, 0);
    for (int i = 1; i <= n; i++){
        if (!mrk[find(i)]){
            dfs_dead(find(i), 0);
        }
    }
    for (int i = 1; i <= m; i++){
        if (rev[i] == 1) cout << "R";
        else if (rev[i] == 2) cout << "L";
        else cout << "B";
    }
    cout << '\n';
    return 0;
}
/*
5 6
1 2
1 2
4 3
2 3
1 3
5 1
2
4 5
1 3
*/

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 3 ms 2796 KB Output is correct
4 Correct 3 ms 2796 KB Output is correct
5 Correct 3 ms 2796 KB Output is correct
6 Correct 3 ms 2796 KB Output is correct
7 Correct 3 ms 2796 KB Output is correct
8 Correct 3 ms 2816 KB Output is correct
9 Correct 3 ms 2836 KB Output is correct
10 Correct 3 ms 2796 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 3 ms 2796 KB Output is correct
4 Correct 3 ms 2796 KB Output is correct
5 Correct 3 ms 2796 KB Output is correct
6 Correct 3 ms 2796 KB Output is correct
7 Correct 3 ms 2796 KB Output is correct
8 Correct 3 ms 2816 KB Output is correct
9 Correct 3 ms 2836 KB Output is correct
10 Correct 3 ms 2796 KB Output is correct
11 Correct 87 ms 8940 KB Output is correct
12 Correct 97 ms 10040 KB Output is correct
13 Correct 106 ms 11500 KB Output is correct
14 Correct 149 ms 12780 KB Output is correct
15 Correct 154 ms 13032 KB Output is correct
16 Correct 146 ms 11236 KB Output is correct
17 Correct 118 ms 13036 KB Output is correct
18 Correct 171 ms 11640 KB Output is correct
19 Correct 125 ms 14312 KB Output is correct
20 Correct 93 ms 9856 KB Output is correct
21 Correct 94 ms 9964 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 3 ms 2796 KB Output is correct
4 Correct 3 ms 2796 KB Output is correct
5 Correct 3 ms 2796 KB Output is correct
6 Correct 3 ms 2796 KB Output is correct
7 Correct 3 ms 2796 KB Output is correct
8 Correct 3 ms 2816 KB Output is correct
9 Correct 3 ms 2836 KB Output is correct
10 Correct 3 ms 2796 KB Output is correct
11 Correct 87 ms 8940 KB Output is correct
12 Correct 97 ms 10040 KB Output is correct
13 Correct 106 ms 11500 KB Output is correct
14 Correct 149 ms 12780 KB Output is correct
15 Correct 154 ms 13032 KB Output is correct
16 Correct 146 ms 11236 KB Output is correct
17 Correct 118 ms 13036 KB Output is correct
18 Correct 171 ms 11640 KB Output is correct
19 Correct 125 ms 14312 KB Output is correct
20 Correct 93 ms 9856 KB Output is correct
21 Correct 94 ms 9964 KB Output is correct
22 Correct 183 ms 14980 KB Output is correct
23 Correct 191 ms 13480 KB Output is correct
24 Correct 212 ms 13412 KB Output is correct
25 Correct 196 ms 17956 KB Output is correct
26 Correct 212 ms 14584 KB Output is correct
27 Correct 189 ms 13540 KB Output is correct
28 Correct 87 ms 7660 KB Output is correct
29 Correct 153 ms 11244 KB Output is correct
30 Correct 156 ms 11884 KB Output is correct
31 Correct 154 ms 11628 KB Output is correct
32 Correct 177 ms 14556 KB Output is correct