Submission #872544

#	Time	Username	Problem	Language	Result	Execution time	Memory
872544		vjudge1	One-Way Streets (CEOI17_oneway)	C++17	30 / 100	3059 ms	5848 KiB

oneway

//author: Ahmet Alp Orakci
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

struct Edge {
    int u, v;
};

#define ONLINE_JUDGE
void solve() {
    int n, m, p;
    cin >> n >> m;

    vector <pair <int, int>> adj[n +1];

    vector <Edge> edges(m);
    for(int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v;

        adj[edges[i].u].emplace_back(edges[i].v, i);
        adj[edges[i].v].emplace_back(edges[i].u, i);
    }
    
    cin >> p;
    vector <pair <int, int>> must(p);
    for(int i = 0; i < p; i++) {
        cin >> must[i].first >> must[i].second;
    }

    auto checkleft = [&](int num) -> bool {
        for(auto &[a, b] : must) {
            vector <bool> vis(n +1);
            queue <int> q;
            q.emplace(a);

            while(!q.empty()) {
                int node = q.front();
                q.pop();
                if(vis[node]) {
                    continue;
                }
                vis[node] = true;

                for(auto [child, edgnum] : adj[node]) {
                    if(edgnum == num) {
                        if(child == edges[edgnum].u) 
                            continue;
                        else
                            q.emplace(child);
                    } else {
                        if(!vis[child])
                            q.emplace(child);
                    }
                }
            }

            if(!vis[b]) {
                return false;
            }
        }

        return true;
    };

    auto checkright = [&](int num) -> bool {
        for(auto &[a, b] : must) {
            vector <bool> vis(n +1);
            queue <int> q;
            q.emplace(a);

            while(!q.empty()) {
                int node = q.front();
                q.pop();
                if(vis[node]) {
                    continue;
                }
                vis[node] = true;

                for(auto [child, edgnum] : adj[node]) {
                    if(edgnum == num) {
                        if(child == edges[edgnum].v) 
                            continue;
                        else
                            q.emplace(child);
                    } else {
                        if(!vis[child])
                            q.emplace(child);
                    }
                }
            }

            if(!vis[b]) {
                return false;
            }
        }

        return true;
    };

    for(int i = 0; i < m; i++) {
        bool res1 = checkleft(i), res2 = checkright(i);
        if(res1 && res2) {
            cout << "B";
        } else if(res1) {
            cout << "R";
        } else if(res2) {
            cout << "L";
        } else {
            cout << "X";
        }
    }
    
    return;
}

signed main() {
    #ifndef ONLINE_JUDGE
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int t = 1; //cin >> t;
    for(int i = 1; i <= t; i++) {
        solve();
    }

    return 0;
}

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