Submission #1259154

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259154		maxil	One-Way Streets (CEOI17_oneway)	C++20	30 / 100	3094 ms	3748 KiB

oneway

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define MASK(x) ((1LL) << (x))
#define BIT(x, i) (((x) >> (i)) & (1LL))
#define str string
#define fi first
#define se second
#define pii pair<int, int>
#define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define endline '\n'
#define all(x) (x).begin(),(x).end()
#define log 20
#define FOR(i,l,r,val) for(int i = l;i <= r ; i = i + val)
#define FORD(i,l,r,val) for(int i = l;i >= r; i = i - val)
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return 1; }; return 0; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return 1; }; return 0; }
using namespace std;

int n, m, p;
vector<pii> edges, must_pairs;

bool check_direction(int fixed_edge, int dir) {
    // dir = 0: edges[fixed_edge] = a->b
    // dir = 1: edges[fixed_edge] = b->a
    
    vector<vector<int>> g(n + 1);
    FOR(i, 0, m - 1, 1) {
        int u = edges[i].fi;
        int v = edges[i].se;
        if (i == fixed_edge) {
            if (dir == 0) g[u].pb(v);
            else g[v].pb(u);
        } else {
            g[u].pb(v);
            g[v].pb(u);
        }
    }

    for (auto [x, y] : must_pairs) {
        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() {
    faster
    cin >> n >> m;
    edges.resize(m);
    FOR(i, 0, m - 1, 1) cin >> edges[i].fi >> edges[i].se;

    cin >> p;
    must_pairs.resize(p);
    FOR(i, 0, p - 1, 1) cin >> must_pairs[i].fi >> must_pairs[i].se;

    str ans = "";
    FOR(i, 0, m - 1, 1) {
        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 << endline;
}

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