oj.uz

Submission #322026

# Submission time Handle Problem Language Result Execution time Memory
322026 2020-11-13T21:46:28 Z Sara One-Way Streets (CEOI17_oneway) C++14
100 / 100
 204 ms 17896 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;
}

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 2796 KB Output is correct
9 Correct 3 ms 2796 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 2796 KB Output is correct
9 Correct 3 ms 2796 KB Output is correct
10 Correct 3 ms 2796 KB Output is correct
11 Correct 79 ms 8940 KB Output is correct
12 Correct 89 ms 9964 KB Output is correct
13 Correct 95 ms 11532 KB Output is correct
14 Correct 115 ms 12780 KB Output is correct
15 Correct 122 ms 13032 KB Output is correct
16 Correct 137 ms 11236 KB Output is correct
17 Correct 114 ms 13036 KB Output is correct
18 Correct 142 ms 11620 KB Output is correct
19 Correct 112 ms 14348 KB Output is correct
20 Correct 91 ms 9660 KB Output is correct
21 Correct 82 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 2796 KB Output is correct
9 Correct 3 ms 2796 KB Output is correct
10 Correct 3 ms 2796 KB Output is correct
11 Correct 79 ms 8940 KB Output is correct
12 Correct 89 ms 9964 KB Output is correct
13 Correct 95 ms 11532 KB Output is correct
14 Correct 115 ms 12780 KB Output is correct
15 Correct 122 ms 13032 KB Output is correct
16 Correct 137 ms 11236 KB Output is correct
17 Correct 114 ms 13036 KB Output is correct
18 Correct 142 ms 11620 KB Output is correct
19 Correct 112 ms 14348 KB Output is correct
20 Correct 91 ms 9660 KB Output is correct
21 Correct 82 ms 9964 KB Output is correct
22 Correct 177 ms 15048 KB Output is correct
23 Correct 176 ms 13412 KB Output is correct
24 Correct 204 ms 13536 KB Output is correct
25 Correct 174 ms 17896 KB Output is correct
26 Correct 173 ms 14564 KB Output is correct
27 Correct 175 ms 13412 KB Output is correct
28 Correct 85 ms 7660 KB Output is correct
29 Correct 146 ms 11244 KB Output is correct
30 Correct 144 ms 11756 KB Output is correct
31 Correct 147 ms 11628 KB Output is correct
32 Correct 150 ms 14444 KB Output is correct