oj.uz

Submission #115067

# Submission time Handle Problem Language Result Execution time Memory
115067 2019-06-05T04:03:42 Z minhtung0404 One-Way Streets (CEOI17_oneway) C++17
100 / 100
 157 ms 25180 KB 
//https://csacademy.com/contest/ceoi-2017-day-1/task/one-way-streets/statement/

#include<bits/stdc++.h>
const int N = 1e5 + 5;
using namespace std;

struct edge{
    int u, v, id;

    edge(int u, int v, int id) : u(u), v(v), id(id) {}
    edge() {}
};

vector <edge> mv;
typedef pair <int, int> ii;
vector <ii> G[N], G2[N];

int n, m, q, pset[N];
int num[N], low[N], cnt, d[N], ans[N];
bool visited[N];
ii p[N];

int Find(int i) {return ((pset[i] == i) ? i : pset[i] = Find(pset[i]));}

void dsu(int u, int v){
    u = Find(u); v = Find(v);
    if (u == v) return;
    pset[v] = u;
}

void dfs(int u, int id){
    num[u] = low[u] = ++cnt;
    for (auto p : G[u]){
        int v = p.first;
        if (id == abs(p.second)) continue;
        if (num[v]) {
            low[u] = min(low[u], num[v]);
            dsu(u, v);
        }
        else {
            dfs(v, abs(p.second));
            low[u] = min(low[u], low[v]);
            if (low[v] <= num[u]) dsu(u, v);
            else{
                mv.push_back(edge(u, v, p.second));
            }
        }
    }
}

void redfs(int u){
    visited[u] = true;
    for(auto x : G2[u]){
        int v = x.first;
        if (visited[v]) continue;
        p[v].first = u; p[v].second = -x.second;
        d[v] = d[u] + 1;
        redfs(v);
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) pset[i] = i;
    for (int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        G[u].push_back(ii(v, i));
        G[v].push_back(ii(u, -i));
    }
    cin >> q;
    for (int i = 1; i <= n; i++) if (!num[i]) dfs(i, 0);
    for (auto ed : mv){
        ed.u = Find(ed.u); ed.v = Find(ed.v);
        G2[ed.u].push_back(ii(ed.v, ed.id));
        G2[ed.v].push_back(ii(ed.u, -ed.id));
    }
    for (int i = 1; i <= n; i++) if (pset[i] == i && !visited[i]) redfs(i);
    while (q--){
        int u, v;
        cin >> u >> v;
        u = Find(u); v = Find(v);
        while (u != v){
            if (d[u] > d[v]) {
                dsu(p[u].first, u);
                ans[abs(p[u].second)] = ((p[u].second > 0) ? 1 : 2);
                u = Find(p[u].first);
            }
            else{
                dsu(p[v].first, v);
                ans[abs(p[v].second)] = ((p[v].second > 0) ? 2 : 1);
                v = Find(p[v].first);
            }
        }
    }
    for (int i = 1; i <= m; i++){
        if (ans[i] == 0) cout << "B";
        if (ans[i] == 1) cout << "R";
        if (ans[i] == 2) cout << "L";
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5120 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 6 ms 5248 KB Output is correct
6 Correct 6 ms 5120 KB Output is correct
7 Correct 6 ms 5192 KB Output is correct
8 Correct 6 ms 5248 KB Output is correct
9 Correct 8 ms 5120 KB Output is correct
10 Correct 7 ms 5180 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5120 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 6 ms 5248 KB Output is correct
6 Correct 6 ms 5120 KB Output is correct
7 Correct 6 ms 5192 KB Output is correct
8 Correct 6 ms 5248 KB Output is correct
9 Correct 8 ms 5120 KB Output is correct
10 Correct 7 ms 5180 KB Output is correct
11 Correct 53 ms 9848 KB Output is correct
12 Correct 66 ms 11256 KB Output is correct
13 Correct 81 ms 13048 KB Output is correct
14 Correct 100 ms 14836 KB Output is correct
15 Correct 96 ms 15460 KB Output is correct
16 Correct 106 ms 16376 KB Output is correct
17 Correct 113 ms 18636 KB Output is correct
18 Correct 121 ms 17740 KB Output is correct
19 Correct 127 ms 21388 KB Output is correct
20 Correct 66 ms 11512 KB Output is correct
21 Correct 57 ms 12176 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5120 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 6 ms 5248 KB Output is correct
6 Correct 6 ms 5120 KB Output is correct
7 Correct 6 ms 5192 KB Output is correct
8 Correct 6 ms 5248 KB Output is correct
9 Correct 8 ms 5120 KB Output is correct
10 Correct 7 ms 5180 KB Output is correct
11 Correct 53 ms 9848 KB Output is correct
12 Correct 66 ms 11256 KB Output is correct
13 Correct 81 ms 13048 KB Output is correct
14 Correct 100 ms 14836 KB Output is correct
15 Correct 96 ms 15460 KB Output is correct
16 Correct 106 ms 16376 KB Output is correct
17 Correct 113 ms 18636 KB Output is correct
18 Correct 121 ms 17740 KB Output is correct
19 Correct 127 ms 21388 KB Output is correct
20 Correct 66 ms 11512 KB Output is correct
21 Correct 57 ms 12176 KB Output is correct
22 Correct 155 ms 20956 KB Output is correct
23 Correct 143 ms 18728 KB Output is correct
24 Correct 138 ms 19064 KB Output is correct
25 Correct 157 ms 25180 KB Output is correct
26 Correct 143 ms 20452 KB Output is correct
27 Correct 128 ms 18924 KB Output is correct
28 Correct 41 ms 8440 KB Output is correct
29 Correct 76 ms 12152 KB Output is correct
30 Correct 73 ms 12920 KB Output is correct
31 Correct 80 ms 12664 KB Output is correct
32 Correct 88 ms 17780 KB Output is correct