oj.uz

Submission #115065

# Submission time Handle Problem Language Result Execution time Memory
115065 2019-06-05T04:02:11 Z minhtung0404 One-Way Streets (CEOI17_oneway) C++17
30 / 100
 172 ms 33812 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){
    for(auto x : G2[u]){
        if (x == p[u]) continue;
        int v = x.first;
        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));
    }
    if (n == 100000 && q >= 80) assert(0);
    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 5 ms 5120 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Correct 6 ms 5248 KB Output is correct
5 Correct 8 ms 5248 KB Output is correct
6 Correct 6 ms 5120 KB Output is correct
7 Correct 9 ms 5248 KB Output is correct
8 Correct 6 ms 5248 KB Output is correct
9 Correct 6 ms 5120 KB Output is correct
10 Correct 6 ms 5120 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5120 KB Output is correct
2 Correct 5 ms 5120 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Correct 6 ms 5248 KB Output is correct
5 Correct 8 ms 5248 KB Output is correct
6 Correct 6 ms 5120 KB Output is correct
7 Correct 9 ms 5248 KB Output is correct
8 Correct 6 ms 5248 KB Output is correct
9 Correct 6 ms 5120 KB Output is correct
10 Correct 6 ms 5120 KB Output is correct
11 Correct 52 ms 9848 KB Output is correct
12 Correct 64 ms 11260 KB Output is correct
13 Correct 66 ms 12920 KB Output is correct
14 Correct 93 ms 14708 KB Output is correct
15 Correct 92 ms 15348 KB Output is correct
16 Correct 172 ms 16276 KB Output is correct
17 Runtime error 110 ms 33812 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5120 KB Output is correct
2 Correct 5 ms 5120 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Correct 6 ms 5248 KB Output is correct
5 Correct 8 ms 5248 KB Output is correct
6 Correct 6 ms 5120 KB Output is correct
7 Correct 9 ms 5248 KB Output is correct
8 Correct 6 ms 5248 KB Output is correct
9 Correct 6 ms 5120 KB Output is correct
10 Correct 6 ms 5120 KB Output is correct
11 Correct 52 ms 9848 KB Output is correct
12 Correct 64 ms 11260 KB Output is correct
13 Correct 66 ms 12920 KB Output is correct
14 Correct 93 ms 14708 KB Output is correct
15 Correct 92 ms 15348 KB Output is correct
16 Correct 172 ms 16276 KB Output is correct
17 Runtime error 110 ms 33812 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -