Submission #1259088

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259088		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;
map<pair<int,int>, int> dir; // hướng của cạnh: (u,v) -> 1 nếu u->v, -1 nếu v->u

bool assign_edge(int a, int b) {
    if (dir[{a,b}] == -1) return false;
    dir[{a,b}] = 1;
    dir[{b,a}] = -1;
    return true;
}

bool bfs_and_direct(int s, int t) {
    vector<int> parent(n+1, -1);
    queue<int> q;
    q.push(s);
    parent[s] = 0;

    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (u == t) break;
        for (int v : adj[u]) {
            if (parent[v] == -1) {
                parent[v] = u;
                q.push(v);
            }
        }
    }

    if (parent[t] == -1) return false; // không tìm được đường đi (không xảy ra nếu đồ thị liên thông)

    // đi ngược lại từ t -> s để định hướng các cạnh
    int cur = t;
    while (cur != s) {
        int par = parent[cur];
        if (!assign_edge(par, cur)) return false; // mâu thuẫn
        cur = par;
    }
    return true;
}

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(v);
        adj[v].push_back(u);
        dir[{u,v}] = dir[{v,u}] = 0; // chưa gán hướng
    }

    bool ok = true;
    for (int i = 0; i < p; i++) {
        int u, v;
        cin >> u >> v;
        if (!bfs_and_direct(u, v)) {
            ok = false;
            break;
        }
    }

    if (!ok) {
        cout << "NO\n";
        return 0;
    }

    cout << "YES\n";
    for (auto &e : edges) {
        if (dir[{e.u, e.v}] == 1) {
            cout << e.u << " " << e.v << "\n";
        } else if (dir[{e.v, e.u}] == 1) {
            cout << e.v << " " << e.u << "\n";
        } else {
            // nếu cạnh không bị ép hướng, ta in theo input
            cout << e.u << " " << e.v << "\n";
        }
    }
    return 0;
}

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