제출 #1165461

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1165461		AlgorithmWarrior	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	133 ms	28928 KiB

oneway

#include <bits/stdc++.h>

using namespace std;

int const MAX=1e5+5;
int const LOG=20;
int n,m;
struct edge{
    int u,v;
}edges[MAX];
struct muchie{
    int vec,id;
};
vector<muchie>tree[MAX];
int h[MAX],low[MAX];
vector<int>critical_edges;
bool viz[MAX];
stack<int>stv;
int grp[MAX];
int total_nodes;
vector<muchie>comp_tree[MAX];
int lift[MAX][LOG];
int up[MAX],down[MAX];
char ans[MAX];

void read(){
    cin>>n>>m;
    int i;
    for(i=1;i<=m;++i){
        int u,v;
        cin>>u>>v;
        edges[i]={u,v};
        tree[u].push_back({v,i});
        tree[v].push_back({u,i});
    }
}

void minself(int& x,int val){
    if(x>val)
        x=val;
}

void dfs_biconex(int nod,int id_p){
    viz[nod]=1;
    low[nod]=h[nod];
    stv.push(nod);
    for(auto [vec,id] : tree[nod])
        if(id!=id_p){
            if(viz[vec])
                minself(low[nod],h[vec]);
            else{
                h[vec]=h[nod]+1;
                dfs_biconex(vec,id);
                minself(low[nod],low[vec]);
            }
        }
    if(low[nod]==h[nod]){
        if(id_p)
            critical_edges.push_back(id_p);
        ++total_nodes;
        while(stv.top()!=nod){
            grp[stv.top()]=total_nodes;
            stv.pop();
        }
        grp[nod]=total_nodes;
        stv.pop();
    }
}

void start_dfs_biconex(){
    int i;
    for(i=1;i<=n;++i)
        if(!viz[i])
            dfs_biconex(i,0);
    for(i=1;i<=n;++i){
        viz[i]=0;
        h[i]=0;
    }
}

void insert_edges(){
    for(auto id : critical_edges){
        auto [u,v] = edges[id];
        u=grp[u];
        v=grp[v];
        comp_tree[u].push_back({v,id});
        comp_tree[v].push_back({u,id});
    }
}

void dfs_init(int nod){
    viz[nod]=1;
    int i;
    for(i=1;i<LOG;++i)
        lift[nod][i]=lift[lift[nod][i-1]][i-1];
    for(auto [fiu,id] : comp_tree[nod])
        if(fiu!=lift[nod][0]){
            lift[fiu][0]=nod;
            h[fiu]=h[nod]+1;
            dfs_init(fiu);
        }
}

void start_dfs_init(){
    int i;
    for(i=1;i<=total_nodes;++i)
        if(!viz[i])
            dfs_init(i);
    for(i=1;i<=total_nodes;++i)
        viz[i]=0;
}

int lca(int u,int v){
    if(h[u]<h[v])
        swap(u,v);
    int dif=h[u]-h[v];
    int i;
    for(i=0;i<LOG;++i)
        if(dif&(1<<i))
            u=lift[u][i];
    if(u==v)
        return u;
    for(i=LOG-1;i>=0;--i)
        if(lift[u][i]!=lift[v][i]){
            u=lift[u][i];
            v=lift[v][i];
        }
    return lift[u][0];
}

void process_queries(){
    int q;
    cin>>q;
    int i;
    for(i=1;i<=q;++i){
        int u,v;
        cin>>u>>v;
        u=grp[u];
        v=grp[v];
        if(u!=v){
            int lc=lca(u,v);
            ++up[u];
            --up[lc];
            ++down[v];
            --down[lc];
        }
    }
}

void dfs_solve(int nod,int id_p){
    viz[nod]=1;
    for(auto [fiu,id] : comp_tree[nod])
        if(fiu!=lift[nod][0]){
            dfs_solve(fiu,id);
            up[nod]+=up[fiu];
            down[nod]+=down[fiu];
        }
    if(up[nod]){
        if(grp[edges[id_p].u]==nod)
            ans[id_p]='R';
        else
            ans[id_p]='L';
    }
    if(down[nod]){
        if(grp[edges[id_p].u]==nod)
            ans[id_p]='L';
        else
            ans[id_p]='R';
    }
}

void start_dfs_solve(){
    int i;
    for(i=1;i<=total_nodes;++i)
        if(!viz[i])
            dfs_solve(i,0);
    for(i=1;i<=total_nodes;++i)
        viz[i]=0;
}

void write(){
    int i;
    for(i=1;i<=m;++i){
        if(!ans[i])
            ans[i]='B';
        cout<<ans[i];
    }
}

int main()
{
    read();
    start_dfs_biconex();
    insert_edges();
    start_dfs_init();
    process_queries();
    start_dfs_solve();
    write();
    return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40