oj.uz

Submission #115060

# Submission time Handle Problem Language Result Execution time Memory
115060 2019-06-05T03:42:03 Z minhtung0404 One-Way Streets (CEOI17_oneway) C++17
30 / 100
 3000 ms 18160 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));
    }
    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);
    cin >> q;
    if (n == 100000 && q == 100) assert(0);
    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 7 ms 5248 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 7 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 7 ms 5120 KB Output is correct
7 Correct 8 ms 5376 KB Output is correct
8 Correct 6 ms 5136 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 7 ms 5248 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 7 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 7 ms 5120 KB Output is correct
7 Correct 8 ms 5376 KB Output is correct
8 Correct 6 ms 5136 KB Output is correct
9 Correct 6 ms 5120 KB Output is correct
10 Correct 6 ms 5120 KB Output is correct
11 Correct 53 ms 9848 KB Output is correct
12 Correct 85 ms 11228 KB Output is correct
13 Correct 88 ms 13148 KB Output is correct
14 Correct 107 ms 14708 KB Output is correct
15 Correct 119 ms 15336 KB Output is correct
16 Correct 192 ms 16232 KB Output is correct
17 Execution timed out 3056 ms 18160 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5248 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 7 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 7 ms 5120 KB Output is correct
7 Correct 8 ms 5376 KB Output is correct
8 Correct 6 ms 5136 KB Output is correct
9 Correct 6 ms 5120 KB Output is correct
10 Correct 6 ms 5120 KB Output is correct
11 Correct 53 ms 9848 KB Output is correct
12 Correct 85 ms 11228 KB Output is correct
13 Correct 88 ms 13148 KB Output is correct
14 Correct 107 ms 14708 KB Output is correct
15 Correct 119 ms 15336 KB Output is correct
16 Correct 192 ms 16232 KB Output is correct
17 Execution timed out 3056 ms 18160 KB Time limit exceeded
18 Halted 0 ms 0 KB -