제출 #1304275

#제출 시각아이디문제언어결과실행 시간메모리
1304275KindaGoodGamesOne-Way Streets (CEOI17_oneway)C++20
0 / 100
186 ms327680 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; 

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+1);
    }
}

int lift(int v, int k){
    for(int i = 0; i <= LGN; i++){
        if(k & (1 << i)){
            v = jumpC[i][v];
        }
    }
    return v;
}

int LCA(int a, int b){
    if(depthC[b] > depthC[a]) swap(a,b);
    a = lift(a, depthC[a]-depthC[b]);

    if(a == b) return a;

    for(int k = LGN; k>= 0; k--){
        if(jumpC[k][a] != jumpC[k][b]){
            a = jumpC[k][a];
            b = jumpC[k][b];
        }
    }
    return jumpC[0][a];
}

void adjust(int v, int t, bool up){
    if(v == t) return;
    adjust(par[v].first,t,up);
    if(up)ans[par[v].second] = 'L'; 
    else ans[par[v].second] = 'R'; 
    par[v] = par[par[v].first];
}
 

int main(){
    int n,m;
    cin >> n >> m;
    low = num = scc = vector<int>(n,-1);
    adj.resize(n);

    vector<pii> edges(m);
    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);
    }
    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);
    jumpC.resize(LGN+1, vector<int>(scccounter));
    depthC.resize(scccounter);
    par.resize(scccounter);
    for(int i = 0 ;i < m; i++){ 
        int a,b;
        tie(a,b) = edges[i];
        if(scc[a] == scc[b]){
            ans[i] = 'B';
        }else{
            adjC[scc[a]].push_back({scc[b],i});
            adjC[scc[b]].push_back({scc[a],i});
        }
    } 

    for(int k = 1; k <= LGN; k++){
        for(int i = 0; i < scccounter; i++){
            jumpC[k][i] = jumpC[k-1][jumpC[k-1][i]];
        }
    }

    DFS(0,0,0);

    for(int i = 0; i < p; i++){
        int a,b;
        tie(a,b) = req[i];
        if(scc[a] == scc[b]) continue;
        int lca = LCA(scc[a],scc[b]); 

        if(lca == scc[a] || lca == scc[b]){
            if(lca == scc[a]) swap(a,b); 
            adjust(scc[a],lca,true);
        }else{
            adjust(scc[a],lca,true);
            adjust(scc[b],lca,false);
        }
    }

    for(int i = 0; i < m; i++){
        int a,b;
        tie(a,b) = edges[i];
        if(depthC[scc[a]] < depthC[scc[b]]) {
            if(ans[i] == 'L') ans[i] = 'R';
            else ans[i] = 'L';
        }
    }

    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...