제출 #1332304

#제출 시각아이디문제언어결과실행 시간메모리
1332304algoproclubOne-Way Streets (CEOI17_oneway)C++20
0 / 100
3093 ms352 KiB
// UUID: 36e9a7be-c512-45e4-a18a-5e8b77c61962
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> critNbrs;
vector<vector<int>> nbrs;
vector<bool> vis;
vector<int> tim, l;
int timePtr;
void dfs(int Index, int Parent=-1) {
    vis[Index]=true;
    tim[Index]=timePtr++;
    l[Index]=tim[Index];
    bool parFound=false;
    for(int i : nbrs[Index]) {
        if(i==Parent && !parFound){
            parFound=true;
            continue;
        }
        if(vis[i]) l[Index]=min(l[Index], tim[i]);
        else{
            dfs(i, Index);
            l[Index]=min(l[Index], l[i]);
            if(tim[Index]<l[i]){
                critNbrs[i].push_back(Index);
                critNbrs[Index].push_back(i);
            }
        }
    }
}

vector<int> compId;
void GenComps(int Index, int ID){
    if(compId[Index]!=-1) return;
    compId[Index]=ID;
    for(int i : nbrs[Index]){
        bool isCutEdge=false;
        for(int j : critNbrs[Index]) if(i==j){
            isCutEdge=true;
            break;
        }
        if(isCutEdge) continue;
        GenComps(i, ID);
    }
}

int compN=0;
vector<vector<array<int, 3>>> compNbrs;
void GenCompEdges(int Index){
    if(vis[Index]) return;
    vis[Index]=true;
    for(int i : nbrs[Index]){
        if(compId[Index]!=compId[i]){
            compNbrs[compId[Index]].push_back({compId[i], Index, i});
        }
        GenCompEdges(i);
    }
}

vector<array<int, 3>> par;
vector<int> timout;
void GenParents(int Index){
    if(vis[Index]) return;
    vis[Index]=true;
    tim[Index]=timePtr++;
    for(auto [i, u, v] : compNbrs[Index]){
        par[i]={Index, u, v};
        GenParents(i);
    }
    timout[Index]=timePtr++;
}

bool IsAncestor(int A, int B){
    return tim[A]<=tim[B] && timout[B]<=timout[A];
}

vector<char> compSol;
void AssignEdges(int A, int B){
    while(!IsAncestor(A, B)){
        compSol[A]='L';
        A=par[A][0];
    }
    while(A!=B){
        compSol[B]='R';
        B=par[B][0];
    }
}

int main() {
    int n, m; cin >> n >> m;
    nbrs.resize(n);
    map<array<int, 2>, int> edgerev;
    for(int i=0;i<m;i++){
        int u, v; cin >> u >> v;
        nbrs[u-1].push_back(v-1);
        edgerev[{u-1, v-1}]=i;
        nbrs[v-1].push_back(u-1);
    }
    vis.resize(n);
    tim.resize(n);
    l.resize(n);
    critNbrs.resize(n);
    for(int i=0;i<n;i++) if(!vis[i]) dfs(i);
    //for(int u=0;u<n;u++) for(auto v : critNbrs[u]) printf("[%d %d]", u+1, v+1);
    compId.resize(n, -1);
    compN=0;
    for(int i=0;i<n;i++) if(compId[i]==-1) GenComps(i, compN++);
    vis.assign(compN, false);
    compNbrs.resize(compN);
    for(int i=0;i<n;i++) GenCompEdges(i);
    //for(int x : compId) printf("%d ", x);
    for(int i=0;i<compN;i++){
        //printf("\n%d: ", i+1);
        //for(auto [j, u, v] : compNbrs[i]) printf(" %d (%d %d)", j+1, u+1, v+1);
    }
    vis.assign(compN, false);
    par.resize(compN);
    tim.resize(compN);
    timout.resize(compN);
    timePtr=0;
    GenParents(0);
    int p; cin >> p;
    compSol.resize(compN, 'B');
    for(int i=0;i<p;i++){
        int u, v; cin >> u >> v;
        AssignEdges(compId[u-1], compId[v-1]);
    }
    vector<char> sol(m, 'B');
    /*for(int i=0;i<compN;i++){
        //printf("%c", compSol[i]);
        int u=par[i][1], v=par[i][2];
        if(0==edgerev.count({u, v})) sol[edgerev[{v, u}]]=(compSol[i]=='L'?'R':'L');
        else sol[edgerev[{u, v}]]=compSol[i];
    }*/
    //printf("\n");
    for(char x : sol) cout << x;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...