oj.uz

Submission #904038

# Submission time Handle Problem Language Result Execution time Memory
904038 2024-01-11T18:15:52 Z selmahbn One-Way Streets (CEOI17_oneway) C++17
0 / 100
 3 ms 4516 KB 
#include <bits/stdc++.h>

using namespace std;

const int INF = numeric_limits<int>::max() / 2;

vector<int> num, low, comp;
stack<int> s;
int dfs_count = 0;
int comp_count = 0;

vector<vector<int>> dir;
vector<int> in;
vector<int> out;

void tarjan_dfs(int current, int parent, vector<vector<int>>& adj) {
    num[current] = low[current] = dfs_count;
    dfs_count++;
    s.push(current);
    for (int neigh : adj[current]) {
        if (num[neigh] == INF) {
            tarjan_dfs(neigh, current, adj);
            low[current] = min(low[current], low[neigh]);
        } else if (neigh != parent) {
            low[current] = min(low[current], num[neigh]);
        }
    }
    if (num[current] == low[current]) {
        while (s.top() != current) {
            int top = s.top();
            s.pop();
            comp[top] = comp_count;
        }
        s.pop();
        comp[current] = comp_count;
        comp_count++;
    }
}

int dir_dfs(int current, vector<int>& visited, vector<vector<int>>& adj) {
    visited[current] = 1;
    int incoming = in[current] - out[current];
    for (int neigh : adj[current]) {
        if (visited[neigh] == 0) {
            int d = dir_dfs(neigh, visited, adj);
            if (d < 0) {
                dir[current][neigh] = -1;
                dir[neigh][current] = 1;
            } else if (d > 0) {
                dir[current][neigh] = 1;
                dir[neigh][current] = -1;
            }
            incoming += d;
        }
    }
    return incoming;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n);
    vector<pair<int, int>> streets;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
        streets.push_back(make_pair(a, b));
    }
    num = vector<int>(n, INF);
    low = vector<int>(n);
    comp = vector<int>(n);
    for (int i = 0; i < n; i++) {
        if (num[i] == INF) {
            tarjan_dfs(i, i, adj);
        }
    }
    adj = vector<vector<int>>(comp_count);
    for (pair<int, int> s : streets) {
        if (comp[s.first] != comp[s.second]) {
            adj[comp[s.first]].push_back(comp[s.second]);
            adj[comp[s.second]].push_back(comp[s.first]);
        }
    }
    in = vector<int>(comp_count, 0);
    out = vector<int>(comp_count, 0);
    int p;
    cin >> p;
    for (int i = 0; i < p; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        if (comp[a] != comp[b]) {
            out[comp[a]]++;
            in[comp[b]]++;
        }
    }
    vector<int> visited(comp_count, 0);
    dir = vector<vector<int>>(comp_count, vector<int>(comp_count, 0));
    for (int i = 0; i < comp_count; i++) {
        if (visited[i] == 0) dir_dfs(i, visited, adj);
    }
    for (pair<int, int> s : streets) {
        if (comp[s.first] == comp[s.second] || dir[comp[s.first]][comp[s.second]] == 0) cout << 'B';
        else if (dir[comp[s.first]][comp[s.second]] == 1) cout << 'R';
        else cout << 'L';
    }
    return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 352 KB Output is correct
4 Correct 3 ms 4456 KB Output is correct
5 Correct 3 ms 4516 KB Output is correct
6 Correct 1 ms 500 KB Output is correct
7 Correct 2 ms 4456 KB Output is correct
8 Correct 2 ms 4456 KB Output is correct
9 Incorrect 1 ms 360 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 352 KB Output is correct
4 Correct 3 ms 4456 KB Output is correct
5 Correct 3 ms 4516 KB Output is correct
6 Correct 1 ms 500 KB Output is correct
7 Correct 2 ms 4456 KB Output is correct
8 Correct 2 ms 4456 KB Output is correct
9 Incorrect 1 ms 360 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 352 KB Output is correct
4 Correct 3 ms 4456 KB Output is correct
5 Correct 3 ms 4516 KB Output is correct
6 Correct 1 ms 500 KB Output is correct
7 Correct 2 ms 4456 KB Output is correct
8 Correct 2 ms 4456 KB Output is correct
9 Incorrect 1 ms 360 KB Output isn't correct
10 Halted 0 ms 0 KB -