oj.uz

답안 #902683

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
902683 2024-01-10T23:57:10 Z selmahbn One-Way Streets (CEOI17_oneway) C++17
0 / 100
 1 ms 348 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]);
            if (num[neigh] == low[neigh]) {
                while (s.top() != neigh) {
                    int top = s.top();
                    s.pop();
                    comp[top] = comp_count;
                }
                s.pop();
                comp[neigh] = comp_count;
                comp_count++;
            }
        } else if (neigh != parent) {
            low[current] = min(low[current], num[neigh]);
        }
    }
}

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 {
                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));
    }
    int p;
    cin >> p;
    vector<pair<int, int>> pairs;
    for (int i = 0; i < p; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        pairs.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);
            while (!s.empty()) {
                int top = s.top();
                s.pop();
                comp[top] = comp_count;
            }
            comp_count++;
        }
    }
    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);
    for (pair<int, int> p : pairs) {
        if (comp[p.first] != comp[p.second]) {
            out[comp[p.first]]++;
            in[comp[p.second]]++;
        }
    }
    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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -