Submission #1335678

#TimeUsernameProblemLanguageResultExecution timeMemory
1335678yc11One-Way Streets (CEOI17_oneway)C++20
0 / 100
181 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<vector<int> > n2;
vector<int> link1;
vector<int> visited1;
vector<int> preorder;
vector<vector<pair<int,int> > > n3;
int c = 0;
int c1 = 0;
vector<int> visited2;
vector<pair<int,int> > edges;
vector<int> pa1;
void dfs1(int x, int p){
    visited1[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 (visited1[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);
    n2.resize(n);
    n1.resize(n);
    visited.assign(n,-1);
    visited1.assign(n,-1);
    visited2.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 (visited1[i]==-1) dfs1(i,-1);
    }
    for (int i = 0;i<n;i++){
        if (visited[i]==-1) dfs(i,-1);
        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));
            }
        }
    }
    depth.resize(n);
    pa.resize(n);
    pa1.resize(n);


    for (int i = 0;i<n;i++) pa[i].assign(20,-1);
    for (int i = 0;i<n;i++){
        if (visited2[cc[i]]==-1) dfs2(cc[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(cc[a],cc[b]);
        while (a!=c){
            int id = pa1[a];
            if (edges[id].first==a) s[id] = 'R';
            else s[id] = 'L';
            a = pa[a][0];
        }
        while (b!=c){
            int id = pa1[b];
            if (edges[id].first==b) s[id] = 'L';
            else s[id] = 'R';
            a = pa[a][0];
        }



    }
    cout<<s;




return 0;


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