제출 #1335702

#제출 시각아이디문제언어결과실행 시간메모리
1335702yc11One-Way Streets (CEOI17_oneway)C++20
0 / 100
187 ms327680 KiB
#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<vector<pair<int,int> > >n1;
vector<int> visited;
vector<int> torder;
vector<int> cc;
vector<int> link1;
vector<int> preorder;
vector<vector<pair<int,int> > > n3;
int c = 0;
int c1 = 0;
vector<pair<int,int> > edges;
vector<int> pa1;
void dfs1(int x, int p){
    visited[x] = 1;
    preorder[x] = c;
    c++;
    link1[x] = c-1;
    for (int i = 0;i<n3[x].size();i++){
        if (n3[x][i].second==p) continue;
        else if (visited[n3[x][i].first]==-1) dfs1(n3[x][i].first,n3[x][i].second);
        else link1[x] = min(link1[x],preorder[n3[x][i].first]);
    }
    }
void dfs(int x, int p){
    visited[x] = 1;
    cc[x] = c1;
    for (int i = 0;i<n3[x].size();i++){
        if (n3[x][i].first==p) continue;
        if (link1[n3[x][i].first]<=preorder[x] and visited[n3[x][i].first]==-1)dfs(n3[x][i].first,x);
    }
    }
vector<vector<int> > pa;
vector<int> dist;
vector<int> depth;
int hi1(int x, int p){
    for (int i = 19;i>=0;i--){
        if ((1<<i)<=p){
            x = pa[x][i];
            p = p-(1<<i);
        }
    }
    return x;
}
int lca(int x, int y){
    if (depth[x]>depth[y]) swap(x,y);
    for (int i = 19;i>=0;i--){
        if (pa[y][i]!=-1 and depth[pa[y][i]]>=depth[x]) y = pa[y][i];
    }
    if (x==y) return x;
    for (int i = 19;i>=0;i--){
        if (pa[x][i]!=pa[y][i]) {
            x = pa[x][i];
            y = pa[y][i];
        }
    }
    return pa[x][0];
}
void dfs2(int x, int p){
    for (int i = 0;i<n1[x].size();i++){
        if (n1[x][i].first!=p){
            depth[n1[x][i].first] = depth[x]+1;
            pa[n1[x][i].first][0] = x;
            pa1[n1[x][i].first] = n1[x][i].second;
            dfs2(n1[x][i].first,x);
        }
    }
}
signed main(){
    int n,m,p;
    cin>>n>>m;
    link1.assign(n,1e9);
    preorder.resize(n);
    n3.resize(n);
    visited.assign(n,-1);
    cc.assign(n,-1);
    for (int i = 0;i<m;i++){
        int a,b;
        cin>>a>>b;
        n3[a-1].push_back(make_pair(b-1,i));
        n3[b-1].push_back(make_pair(a-1,i));
        edges.push_back(make_pair(a-1,b-1));
    }
    for (int i = 0;i<n;i++){

        if (visited[i]==-1) dfs1(i,-1);
    }
    visited.clear();
    visited.assign(n,-1);
    for (int i = 0;i<n;i++){
        if (visited[i]==-1) dfs(i,-1);
        c1++;
    }
    n1.resize(c1);
    depth.resize(c1);
    pa.resize(c1);
    pa1.resize(c1);
    for (int i = 0;i<n;i++){
        for (int j = 0;j<n3[i].size();j++){
            if (link1[n3[i][j].first]>preorder[i]){
                n1[cc[i]].push_back(make_pair(cc[n3[i][j].first],n3[i][j].second));
                n1[cc[n3[i][j].first]].push_back(make_pair(cc[i],n3[i][j].second));
            }
        }
    }




    for (int i = 0;i<c1;i++) pa[i].assign(20,-1);
    visited.clear();
    visited.assign(n,-1);
    for (int i = 0;i<n;i++){
        if (visited[cc[i]]==-1) dfs2(cc[i],-1);
    }
    for (int i = 1;i<20;i++){
        for (int j = 0;j<c1;j++){
            if (pa[j][i-1]!=-1) pa[j][i] = pa[pa[j][i-1]][i-1];
            else pa[j][i] = -1;
        }
    }
    string s = "";
    for (int i = 0;i<m;i++) s = s+'B';
    cin>>p;
    for (int i = 0;i<p;i++){
        int a,b;
        cin>>a>>b;
        a = cc[a-1];
        b =cc[b-1];
        int c = lca(a,b);
        while (a!=c){
            int id = pa1[a];
        if (id==-1) break;
            if (cc[edges[id].first]==a) s[id] = 'R';
            else s[id] = 'L';
            a = pa[a][0];
        }
        while (b!=c){
            int id = pa1[b];
            if (id==-1) break;
            if (cc[edges[id].first]==b) s[id] = 'L';
            else s[id] = 'R';
            b = pa[b][0];
        }



    }
    cout<<s;




return 0;


    }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...