제출 #1259089

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1259089		maxil	One-Way Streets (CEOI17_oneway)	C++20	30 / 100	3097 ms	3752 KiB

oneway

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

int n, m, p;
vector<pair<int,int>> edges;
vector<pair<int,int>> must;

bool check_direction(int fixed_edge, int dir) {
    // dir = 0: edges[fixed_edge] = a->b
    // dir = 1: edges[fixed_edge] = b->a
    
    // Xây đồ thị có hướng tạm
    vector<vector<int>> g(n+1);
    for (int i = 0; i < m; i++) {
        int u = edges[i].first;
        int v = edges[i].second;
        if (i == fixed_edge) {
            if (dir == 0) g[u].push_back(v);
            else g[v].push_back(u);
        } else {
            // cho cả 2 chiều
            g[u].push_back(v);
            g[v].push_back(u);
        }
    }

    // Kiểm tra tất cả cặp (x, y)
    for (auto [x, y] : must) {
        vector<int> vis(n+1, 0);
        queue<int> q;
        q.push(x);
        vis[x] = 1;
        bool ok = false;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            if (u == y) { ok = true; break; }
            for (int nxt : g[u]) {
                if (!vis[nxt]) {
                    vis[nxt] = 1;
                    q.push(nxt);
                }
            }
        }
        if (!ok) return false;
    }
    return true;
}

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

    cin >> n >> m;
    edges.resize(m);
    for (int i = 0; i < m; i++) {
        cin >> edges[i].first >> edges[i].second;
    }
    cin >> p;
    must.resize(p);
    for (int i = 0; i < p; i++) {
        cin >> must[i].first >> must[i].second;
    }

    string ans = "";
    for (int i = 0; i < m; i++) {
        bool okR = check_direction(i, 0);
        bool okL = check_direction(i, 1);
        if (okR && okL) ans += 'B';
        else if (okR) ans += 'R';
        else ans += 'L';
    }
    cout << ans << "\n";
}

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