제출 #1304630

#제출 시각아이디문제언어결과실행 시간메모리
1304630KindaGoodGamesOne-Way Streets (CEOI17_oneway)C++20
0 / 100
1 ms332 KiB
/*
    Mistakes:
    1. Assumed that condensed Graph was just a tree, but it is a forest, as the original Graph could be not connected.
    2. Did weird thing to determine bridge-direction (similiar to DSU), but doing the directing offline by sorting in ascending depth of lca is
    easier than original approach.
*/
#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<pii>> 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,ind] : adj[v]){
        if(ind == p) continue;
        if(num[u] == -1){
            Tarjan(u,ind);
            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;

char inv(char a){
    if(a == 'L') return 'R';
    return 'L';
}

void DFS(int v, int p, int d, vector<bool>& vis){
    vis[v] = true;
    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,vis);
    }
}

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 d, bool up){ 
    if(depthC[v] <= d) {
        return;
    }
    if(ans[par[v].second] != 0) return;
    ans[par[v].second] = 'L';
    if(scc[edges[par[v].second].second] == v)  ans[par[v].second]  = inv(ans[par[v].second] );
    if(up)  ans[par[v].second]  = inv(ans[par[v].second] ); 
    adjust(par[v].first,d,up);
    par[v] = par[par[v].first];
}
 

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

    edges.resize(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,i});
        adj[b].push_back({a,i});
        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);
    depthC.resize(scccounter);
    par.resize(scccounter);
    jumpC.resize(LGN+1, vector<int>(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});
        }
    } 
    vector<bool> vis(scccounter);
    for(int i = 0; i < scccounter; i++){
        if(vis[i]) continue;
        DFS(i,i,0,vis);
    }

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

    vector<tiii> q;
    for(int i = 0; i < p; i++){
        int a,b;
        tie(a,b) = req[i]; 
        int lca = LCA(scc[a],scc[b]); 

        q.push_back({scc[a],depthC[lca],true});
        q.push_back({scc[b],depthC[lca],false}); 
    }

    sort(q.begin(),q.end(), [](tiii a, tiii b){return get<1>(a) < get<1>(b);});

    for(auto [a,d,up] : q){
        adjust(a,d,up);
    }

    for(int i = 0; i < m; i++){
        int a,b;
        tie(a,b) = edges[i];
        if(freq[{min(a,b),max(a,b)}] >= 2){
            ans[i] = 'B'; 
        }
        if(ans[i] != 'L' && ans[i] != 'R'){
            ans[i] = 'B';
        }
    }
 
    for(int i = 0; i < m; i++){
        assert(ans[i] == 'B' || ans[i] == 'R' || ans[i] == 'L'); 
        cout << ans[i];
    }
    cout << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...