oj.uz

Submission #249074

# Submission time Handle Problem Language Result Execution time Memory
249074 2020-07-14T09:46:03 Z Sorting One-Way Streets (CEOI17_oneway) C++17
60 / 100
 3000 ms 11768 KB 
#include <bits/stdc++.h>

using namespace std;

const int k_N = 1e5 + 3;

int n, m, p;
vector<pair<int, int>> adjacent[k_N];
pair<int, int> edges[k_N];

bool used[k_N];
int depth[k_N];
char ans[k_N];

int cycle(int node, int p_idx){
    used[node] = true;

    int ret = node;
    for(auto [to, idx]: adjacent[node]){
        if(idx == p_idx)
            continue;
        if(used[to]){
            ans[idx] = 'B';
            if(depth[to] < depth[ret]) ret = to;
        }
        else{
            depth[to] = depth[node] + 1;
            int x = cycle(to, idx);
            if(x != to) ans[idx] = 'B';
            if(depth[x] < depth[ret]) ret = x;
        }
    }

    return ret;
}

bool dfs(int start, int end){
    used[start] = true;
    if(start == end)
        return true;

    for(auto [to, idx]: adjacent[start]){
        if(used[to])
            continue;
        if(dfs(to, end)){
            if(ans[idx] != 'B'){
                if(edges[idx].first == start) ans[idx] = 'R';
                else ans[idx] = 'L';
            }
            return true;
        }
    }
    return false;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    for(int i = 0; i < m; ++i){
        int u, v;
        cin >> u >> v;

        adjacent[u].push_back({v, i});
        adjacent[v].push_back({u, i});
        ans[i] = 'U';
        edges[i] = {u, v};
    }

    for(int i = 1; i <= n; ++i){
        if(!used[i]){
            depth[i] = 0;
            cycle(i, -1);
        }
    }

    cin >> p;
    for(int i = 0; i < p; ++i){
        int u, v;
        cin >> u >> v;

        for(int j = 1; j <= n; ++j)
            used[j] = false;
        dfs(u, v);
    }

    for(int i = 0; i < m; ++i)
        if(ans[i] == 'U')
            ans[i] = 'B';

    for(int i = 0; i < m; ++i)
        cout << ans[i];
    cout << "\n";
}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 3 ms 2816 KB Output is correct
4 Correct 2 ms 2816 KB Output is correct
5 Correct 3 ms 2816 KB Output is correct
6 Correct 3 ms 2816 KB Output is correct
7 Correct 3 ms 2816 KB Output is correct
8 Correct 4 ms 2816 KB Output is correct
9 Correct 3 ms 2816 KB Output is correct
10 Correct 3 ms 2816 KB Output is correct
11 Correct 97 ms 8824 KB Output is correct
12 Correct 164 ms 9720 KB Output is correct
13 Correct 259 ms 10488 KB Output is correct
14 Correct 292 ms 11004 KB Output is correct
15 Correct 301 ms 11000 KB Output is correct
16 Correct 59 ms 9080 KB Output is correct
17 Correct 215 ms 10616 KB Output is correct
18 Correct 169 ms 9080 KB Output is correct
19 Correct 287 ms 11768 KB Output is correct
20 Correct 221 ms 9080 KB Output is correct
21 Correct 189 ms 8824 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 3 ms 2816 KB Output is correct
4 Correct 2 ms 2816 KB Output is correct
5 Correct 3 ms 2816 KB Output is correct
6 Correct 3 ms 2816 KB Output is correct
7 Correct 3 ms 2816 KB Output is correct
8 Correct 4 ms 2816 KB Output is correct
9 Correct 3 ms 2816 KB Output is correct
10 Correct 3 ms 2816 KB Output is correct
11 Correct 97 ms 8824 KB Output is correct
12 Correct 164 ms 9720 KB Output is correct
13 Correct 259 ms 10488 KB Output is correct
14 Correct 292 ms 11004 KB Output is correct
15 Correct 301 ms 11000 KB Output is correct
16 Correct 59 ms 9080 KB Output is correct
17 Correct 215 ms 10616 KB Output is correct
18 Correct 169 ms 9080 KB Output is correct
19 Correct 287 ms 11768 KB Output is correct
20 Correct 221 ms 9080 KB Output is correct
21 Correct 189 ms 8824 KB Output is correct
22 Execution timed out 3091 ms 11028 KB Time limit exceeded
23 Halted 0 ms 0 KB -