Submission #1268054

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268054		Sofiatpc	One-Way Streets (CEOI17_oneway)	C++20	60 / 100	3096 ms	18756 KiB

oneway

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define sc second
#define sz(v) (int)v.size()
const int MAXN = 1*1e5+5;
vector< pair<int,int> > adj[MAXN], adj2[MAXN];
int pai[MAXN], s[MAXN], dist[MAXN], low[MAXN], nxt[MAXN];
int u[MAXN], v[MAXN], ans[MAXN]; //1 R 2 L

int find(int x){
    if(pai[x] == x)return x;
    return pai[x] = find(pai[x]);
}

void merge(int a, int b){
    a = find(a), b = find(b);
    if(a == b)return;
    if(s[a] < s[b])swap(a,b);
    pai[b] = a;
    s[a] += s[b];
}

void dfs(int s, int p){
    low[s] = dist[s];

    int qtd = 0;
    for(int i = 0; i < sz(adj[s]); i++){
        int viz = adj[s][i].fi;

        if(qtd == 0 && viz == p){qtd++; continue;}
        if(dist[viz])low[s] = min(low[s],low[viz]);
        else{
            dist[viz] = dist[s]+1;
            dfs(viz,s);
            low[s] = min(low[s],low[viz]);

            if(low[viz] <= dist[s])merge(s,viz);
        }
    }
}

void dfs2(int s){
    for(int i = 0; i < sz(adj2[s]); i++){
        int viz = adj2[s][i].fi, id = adj2[s][i].sc;
        if(id != nxt[s]){
            nxt[viz] = id;
            dist[viz] = dist[s]+1;
            dfs2(viz);
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n,m; cin>>n>>m;
    for(int i = 1; i <= n; i++){
        pai[i] = i; s[i] = 1;
    }

    for(int i = 1; i <= m; i++){
        cin>>u[i]>>v[i];
        adj[u[i]].emplace_back(v[i],i); 
        adj[v[i]].emplace_back(u[i],i);
    }

    for(int i = 1; i <= n; i++)
        if(dist[i] == 0){
            dist[i] = 1;
            dfs(i,0);
        }
    
    for(int i = 1; i <= n; i++){
        int repi = find(i);
        for(int j = 0; j < sz(adj[i]); j++){
            int viz = adj[i][j].fi, id = adj[i][j].sc;

            int repviz = find(viz);
            if(i < viz && repi != repviz){
                if(u[id] == i){u[id] = repi; v[id] = repviz;}
                else {u[id] = repviz; v[id] = repi;}

                adj2[repi].emplace_back(repviz,id);
                adj2[repviz].emplace_back(repi,id);
            }
        }

        dist[i] = 0;
    }
    
    for(int i = 1; i <= n; i++)
        if(dist[i] == 0){
            dist[i] = 1;
            dfs2(i);
        }  

    int q; cin>>q;
    while(q--){
        int a,b; cin>>a>>b;
        a = find(a), b = find(b);

        while(a != b){
            if(dist[a] > dist[b]){
                if(u[nxt[a]] == a){
                    ans[nxt[a]] = 1;
                    a = v[nxt[a]];
                }else{
                    ans[nxt[a]] = 2;
                    a = u[nxt[a]];
                }
            }else{
                if(u[nxt[b]] == b){
                    ans[nxt[b]] = 2;
                    b = v[nxt[b]];
                }else{
                    ans[nxt[b]] = 1;
                    b = u[nxt[b]];
                }
            }
        }
    }

    for(int i = 1; i <= m; i++){
        if(ans[i] == 0)cout<<"B";
        else if(ans[i] == 1)cout<<"R";
        else cout<<"L";
    }
    cout<<"\n";
}

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