oj.uz

Submission #526109

# Submission time Handle Problem Language Result Execution time Memory
526109 2022-02-13T18:33:41 Z Josia One-Way Streets (CEOI17_oneway) C++14
0 / 100
 0 ms 312 KB 
#include <bits/stdc++.h>

using namespace std;

#define int int64_t

int n, m;
vector<vector<int>> graph;
map<pair<int, int>, int> indexOfEdge;
vector<bool> turnedAround;
void readInput1() {
    cin >> n >> m;
    graph.resize(n);

    for (int i = 0; i<m; i++) {
        int a, b; cin >> a >> b; a--; b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
        indexOfEdge[{min(a, b), max(a, b)}] = i;
        turnedAround.push_back(a>b);
    }
}

int timer = 0;
vector<int> pre, back;
set<pair<int, int>> bridges;
void dfs(int v, int p) {
    pre[v] = back[v] = timer;
    timer ++;

    bool didParent = 0;
    for (int w: graph[v]) {
        if (w == p && !didParent) {didParent = 1; continue;}
        if (pre[w] != -1) {
            back[v] = min(back[v], pre[w]);
            continue;
        }

        dfs(w, v);

        back[v] = min(back[v], back[w]);

        if (back[w] > pre[v]) {
            bridges.insert({min(v, w), max(v, w)});
        }
    }
}

vector<int> group;
int groupCount = -1;
void compress(int v) {
    if (group[v] != -1) return;
    group[v] = groupCount;
    for (int w: graph[v]) {
        if (group[w] != -1) continue;
        if (bridges.count({min(v, w), max(v, w)})) continue;
        compress(w);
    }
}

vector<vector<pair<int, int>>> tree;
void makeTree() {
    for (auto i: bridges) {
        tree[group[i.first]].push_back({group[i.second], indexOfEdge[{min(i.first, i.second), max(i.first, i.second)}]});
        tree[group[i.second]].push_back({group[i.first], indexOfEdge[{min(i.first, i.second), max(i.first, i.second)}]});
    }
}

int p;
vector<vector<pair<int, bool>>> pairs;
void readInput2() {
    cin >> p;

    for (int i = 0; i<p; i++) {
        int a, b; cin >> a >> b; a--; b--;
        pairs[group[a]].push_back({group[b], 0});
        pairs[group[b]].push_back({group[a], 1});
    }
}

vector<int> direction;  // 2: both; 0: normal; 1: reversed;
vector<bool> visited;
void compute(int v, int p, int edgeIndex) {
    if (visited[v]) return;
    visited[v] = 1;

    for (auto w: tree[v]) {
        if (visited[w.first]) continue;
        compute(w.first, v, w.second);
    }


    if (edgeIndex != -1 && pairs[v].size()) {
        direction[edgeIndex] = v < p != !pairs[v][0].second;
        pairs[p].push_back({pairs[v][0].first, pairs[v][0].second});
    }
}


signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    readInput1();

    pre.assign(n, -1);
    back.assign(n, -1);
    dfs(0, -1);

    group.assign(n, -1);
    for (int i = 0; i<n; i++) {
        if (group[i] != -1) continue;
        groupCount++;
        compress(i);
    }

    tree.resize(groupCount+1);
    makeTree();

    // for (auto i: tree) {
    //     for (auto j: i) {
    //         cerr << j.first << ";" << j.second << " ";
    //     } cerr << "\n";
    // }

    pairs.resize(groupCount+1);
    readInput2();

    direction.assign(m, 2);
    visited.assign(n, 0);
    compute(0, -1, -1);

    for (int i = 0; i<m; i++) {
        if (direction[i] == 2) cout << "B";
        else if (direction[i] == turnedAround[i]) cout << "R";
        else cout << "L";
    } cout << "\n";

    // for (int i: direction) {
    //     cerr << i;
    // } cerr << "\n";

    // cerr << "IndexOfEdge (1, 5): " << indexOfEdge[{3-1, 4-1}] << "\n";

    return 0;
}

Compilation message

oneway.cpp: In function 'void compute(int64_t, int64_t, int64_t)':
oneway.cpp:94:34: warning: suggest parentheses around comparison in operand of '!=' [-Wparentheses]
   94 |         direction[edgeIndex] = v < p != !pairs[v][0].second;
      |                                ~~^~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 312 KB Output isn't correct
2 Halted 0 ms 0 KB -