Submission #1259109

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259109		maxil	One-Way Streets (CEOI17_oneway)	C++20	0 / 100	0 ms	320 KiB

oneway

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int u, v;
};

int n, m, p;
vector<Edge> edges;
vector<vector<int>> adj;
vector<pair<int,int>> queries;
vector<char> orient; // 'B', 'L', 'R'
bool possible = true;

// lưu hướng bị ép: 0 = chưa, 1 = u->v, 2 = v->u
vector<int> forced;

void force_edge(int id, int dir) {
    if (forced[id] == 0) forced[id] = dir;
    else if (forced[id] != dir) possible = false;
}

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

    cin >> n >> m >> p;
    edges.resize(m);
    adj.assign(n+1, {});
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        edges[i] = {u, v};
        adj[u].push_back(i);
        adj[v].push_back(i);
    }
    queries.resize(p);
    for (int i = 0; i < p; i++) {
        cin >> queries[i].first >> queries[i].second;
    }

    orient.assign(m, 'B');
    forced.assign(m, 0);

    // xử lý từng truy vấn (sub2: p nhỏ nên BFS được)
    for (auto [s, t] : queries) {
        // BFS vô hướng
        vector<int> parent(n+1, -1);
        vector<int> pedge(n+1, -1);
        queue<int> q;
        q.push(s);
        parent[s] = s;
        while (!q.empty() && parent[t] == -1) {
            int u = q.front(); q.pop();
            for (int id : adj[u]) {
                int v = edges[id].u ^ edges[id].v ^ u; // lấy đỉnh kia
                if (parent[v] == -1) {
                    parent[v] = u;
                    pedge[v] = id;
                    q.push(v);
                }
            }
        }
        if (parent[t] == -1) {
            cout << "NIE\n";
            return 0;
        }

        // Truy ngược từ t về s để ép hướng cạnh
        int cur = t;
        while (cur != s) {
            int id = pedge[cur];
            int u = edges[id].u, v = edges[id].v;
            if (parent[cur] == u && cur == v) {
                // đi u->v
                force_edge(id, 1);
            } else if (parent[cur] == v && cur == u) {
                // đi v->u
                force_edge(id, 2);
            }
            cur = parent[cur];
        }

        if (!possible) {
            cout << "NIE\n";
            return 0;
        }
    }

    // in kết quả
    for (int i = 0; i < m; i++) {
        if (forced[i] == 1) orient[i] = 'R'; // u->v
        else if (forced[i] == 2) orient[i] = 'L'; // v->u
        else orient[i] = 'B';
    }
    for (char c : orient) cout << c;
    cout << "\n";
    return 0;
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40