oj.uz

Submission #938263

# Submission time Handle Problem Language Result Execution time Memory
938263 2024-03-05T03:53:33 Z vjudge1 One-Way Streets (CEOI17_oneway) C++17
0 / 100
 3000 ms 348 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    auto G = [&](int n, auto E, auto P){
        int m = E.size();
        for ( auto &[u, v]: E ){
            --u, --v;
        }
        for ( auto &[x, y]: P ){
            --x, --y;
        }
        vector <ar<int,2>> ok(m);
        for ( int mask = 0; mask < 1 << m; mask++ ){
            vector <vector<int>> G(n);
            for ( int i = 0; i < m; i++ ){
                auto [u, v] = E[i];
                if ( mask >> i & 1 ){
                    G[v].pb(u);
                } else G[u].pb(v);
            }
            vector <int> us(n);
            int des = -1;
            auto dfs = [&](auto dfs, int u) -> bool{
                if ( u == des ){
                    return true;
                }
                us[u] = true;
                for ( auto &v: G[u] ){
                    if ( !us[v] && dfs(dfs, v) ){
                        return true;
                    }
                }
                return false;
            };
            bool flag = true;
            for ( auto &[x, y]: P ){
                us.assign(n, 0);
                des = y;
                if ( !dfs(dfs, x) ){
                    flag = false;
                    break;
                }
            }
            if ( !flag ) continue;
            for ( int i = 0; i < m; i++ ){
                ok[i][mask >> i & 1] |= true;
            }
        }
        string ret = string(m, '#');
        for ( int i = 0; i < m; i++ ){
            if ( ok[i][0] && ok[i][1] ){
                ret[i] = 'B';
            } else if ( ok[i][0] ){
                ret[i] = 'R';
            } else if ( ok[i][1] ){
                ret[i] = 'L';
            } else{
                ret = string(m, '#');
                break;
            }
        }
        return ret;
    };
    int n, m; cin >> n >> m;
    vector <ar<int,2>> E(m);
    for ( auto &[u, v]: E ){
        cin >> u >> v;
    }
    int p; cin >> p;
    vector <ar<int,2>> P(p);
    for ( auto &[x, y]: P ){
        cin >> x >> y;
    }
    cout << G(n, E, P);

    cout << '\n';
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3061 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3061 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3061 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -