Submission #1304319

#TimeUsernameProblemLanguageResultExecution timeMemory
1304319KindaGoodGamesOne-Way Streets (CEOI17_oneway)C++20
30 / 100
3095 ms22976 KiB
#include<bits/stdc++.h>

#define ll long long
#define pii pair<int,int>
#define tiii tuple<int,int,int>

using namespace std;

int LGN = 22;

vector<vector<int>> adj;
vector<int> num, low, scc;
int counter = 0;
int scccounter = 0;
stack<int> S; 
vector<char> ans; 
vector<pii> edges;

void Tarjan(int v, int p){
    num[v] = low[v] = counter++;
    S.push(v);
    for(auto u : adj[v]){
        if(u == p) continue;
        if(num[u] == -1){
            Tarjan(u,v);
            low[v] = min(low[v], low[u]);
        }else{
            low[v] = min(low[v], num[u]);
        }
    }

    if(num[v] == low[v]){
        int u;
        do{
            u = S.top();S.pop();
            scc[u] = scccounter;
        }while(v != u);
        scccounter++;
    }
}

//  ---- 

vector<vector<pii>> adjC;
vector<int> depthC;
vector<vector<int>> jumpC; 
vector<pii> par;

void DFS(int v, int p, int d){
    depthC[v] = d++;
    jumpC[0][v] = p;
    for(auto u : adjC[v]){
        if(u.first == p) continue;
        par[u.first] = {v,u.second};
        DFS(u.first,v,d);
    }
}
 

bool search(int v, int p, int t){
    if(v == t) return true;

    for(auto [u,ind] : adjC[v]){
        if(u == p) continue;
        if(search(u,v,t)){
            if(scc[edges[ind].first] == v){ 
                ans[ind] = 'R';
            }
            else {
                ans[ind] = 'L';
            }
            return true;
        }
    }
    return false;
} 

int main(){
    int n,m;
    cin >> n >> m;
    low = num = scc = vector<int>(n,-1);
    adj.resize(n);
    edges.resize(m);
    map<pii,int> freq;
    for(int i = 0; i < m; i++){
        int a,b;
        cin >> a >> b;
        a--;b--;
        edges[i] = {a,b};
        adj[a].push_back(b);
        adj[b].push_back(a);
        freq[{min(a,b),max(a,b)}]++;
    }
    int p;
    cin >> p;
    vector<pii> req(p);
    ans.resize(m);
    for(int i = 0; i < p; i++){
        int a,b;
        cin >> a >> b;
        a--;b--;
        req[i] = {a,b};
    }

    for(int i = 0; i < n; i++){
        if(num[i] == -1){
            Tarjan(i,i);
        }
    }
    
    adjC.resize(scccounter); 
    for(int i = 0 ;i < m; i++){ 
        int a,b;
        tie(a,b) = edges[i];
        if(scc[a] != scc[b]){
            adjC[scc[a]].push_back({scc[b],i});
            adjC[scc[b]].push_back({scc[a],i});
        }
    } 
    
    for(auto [a,b] : req){ 
        search(scc[a],scc[a],scc[b]);
    }

    for(int i = 0; i < m; i++){ 
        int a,b;
        tie(a,b) = edges[i];
        if(ans[i] != 'L' && ans[i] != 'R'){
            ans[i] = 'B';
        }
        if(freq[{min(a,b),max(a,b)}] >= 2){
            ans[i] = 'B'; 
        }
    }

    for(int i = 0; i < m; i++){
        cout << ans[i];
    }
    cout << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...