oj.uz

Submission #51829

# Submission time Handle Problem Language Result Execution time Memory
51829 2018-06-21T12:17:39 Z istlemin One-Way Streets (CEOI17_oneway) C++14
0 / 100
 3000 ms 380 KB 
#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define trav(a,c) for(auto a: c)

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;

vector<bool> seen;
vector<vi> e;

void dfs(ll v){
    if(seen[v]) return;
    seen[v] = true;
    rep(i,0,e[v].size()) dfs(e[v][i]);
}

int main(){
	cin.sync_with_stdio(false);
    ll n,m;
	cin>>n>>m;
    vector<pii> edgeList(m);
	e.resize(n);
    rep(i,0,m){
        cin>>edgeList[i].first>>edgeList[i].second;
        --edgeList[i].first; --edgeList[i].second;
    }

    ll p; cin>>p;
    vector<pii> ps(p);
    rep(i,0,p){
        cin>>ps[i].first>>ps[i].second;
        --ps[i].first; --ps[i].second;
    }

    vi allSol;

    rep(mask,0,(1<<m)){
        e.assign(n,vi(0));
        rep(i,0,m){
            if(mask&(1<<i)) e[edgeList[i].first].push_back(edgeList[i].second);
            else e[edgeList[i].second].push_back(edgeList[i].first);
        }

        bool val = true;

        rep(i,0,p){
            seen.assign(n,false);
            dfs(ps[i].first);
            val &= (seen[ps[i].second]);
        }

        if(val){
            allSol.push_back(mask);
            //cout<<mask<<endl;
        }
    }

    assert(allSol.size()>0);

    rep(i,0,m){
        bool any0 = false;
        bool any1 = false;
        rep(j,0,allSol.size()){
            if(allSol[j]&(1<<i)) any1 = true;
            else any0 = true;
        }
        if(any0&&any1) cout<<"B";
        else if(any0) cout<<"L";
        else cout<<"R";
    }
    cout<<endl;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3034 ms 380 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 3034 ms 380 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 3034 ms 380 KB Time limit exceeded
2 Halted 0 ms 0 KB -