제출 #1335723

#제출 시각아이디문제언어결과실행 시간메모리
1335723yc11One-Way Streets (CEOI17_oneway)C++20
0 / 100
1 ms344 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<int> up;
vector<int> down;
vector<vector<pair<int,int> > > n3;
int c = 0;
int c1 = 0;
string s ="";
vector<pair<int,int> > edges;
vector<int> pa1;
vector<int> hi;
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);
            link1[x] = min(link1[x],link1[n3[x][i].first]);
        }
        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].second==p) continue;
        if (link1[n3[x][i].first]<=preorder[x] and visited[n3[x][i].first]==-1)dfs(n3[x][i].first,n3[x][i].second);
    }
    }
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){
    visited[x] = 1;
    for (int i = 0;i<n1[x].size();i++){
        if (n1[x][i].first!=p and visited[n1[x][i].first]==-1){
            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);
        }
    }
}
void dfs3(int x, int p) {
    for (int i = 0; i < n1[x].size(); i++) {
        int y = n1[x][i].first;
        int id = n1[x][i].second;
        if (y == p) continue;

        dfs3(y, x);

        up[x] += up[y];
        down[x] += down[y];

        if (up[y] > 0 && down[y] > 0) {
            s[id] = 'B';
        } else if (up[y] > 0) {
            if (x == hi[id]) s[id] = 'R';
            else s[id] = 'L';
        } else if (down[y] > 0) {
            if (x == hi[id]) s[id] = 'L';
            else s[id] = 'R';
        } else {
            s[id] = 'B';
        }
    }
}

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);
    n1.resize(c1);

    hi.resize(m, -1);
for (int id = 0; id < m; id++) {
    int u = edges[id].first;
    int v = edges[id].second;
    int cu = cc[u];
    int cv = cc[v];
    if (cu != cv) {
        n1[cu].push_back(make_pair(cv, id));
        n1[cv].push_back(make_pair(cu, id));
        hi[id] = cu; // store the first component as per input
    }
}





    for (int i = 0;i<c1;i++) pa[i].assign(20,-1);
    visited.clear();
    visited.assign(c1,-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;
        }
    }

    for (int i = 0;i<m;i++) s = s+'B';
    cin>>p;

    up.assign(c1,0);
    down.assign(c1,0);
    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);

    up[a]++;
    up[c]--;

    down[b]++;
    down[c]--;
}
for (int i = 0;i<c1;i++){
    if (pa[i][0]==-1){
        dfs3(i,-1);
    }
}
    cout<<s;




return 0;


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