제출 #1282382

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1282382		warrenn	One-Way Streets (CEOI17_oneway)	C++20	0 / 100	1 ms	332 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
#define int long long
#pragma GCC optimize("O3,unroll-loops")

const int maxn = 1e5;
int n, m;
vector<pair<int,int>> adj[maxn+2];
int dsu[maxn+2], val[maxn+2], vis[maxn+2];
int bridge[maxn+2], disc[maxn+2], low[maxn+2], ans[maxn+2];
pair<int,int> road[maxn+2];
int timer = 0;

int fin(int a){
    return dsu[a]==a ? a : dsu[a]=fin(dsu[a]);
}
void merg(int a,int b){
    a=fin(a); b=fin(b);
    if(a!=b) dsu[a]=b;
}

void dfs(int u,int parentEdge){
    disc[u] = low[u] = ++timer;
    for(auto [v,id] : adj[u]){
        if(id == parentEdge) continue;
        if(!disc[v]){
            dfs(v,id);
            low[u] = min(low[u], low[v]);
            if(low[v] > disc[u]) bridge[id] = 1;
        } else {
            low[u] = min(low[u], disc[v]);
        }
    }
}

void dfs2(int u,int p){
    vis[u]=1;
    for(auto [v,id]: adj[u]){
        if(v==p) continue;
        dfs2(v,u);
        val[u]+=val[v];
        if(val[v]>0){
            ans[id] = (road[id].first==u)?2:1;
        } else if(val[v]<0){
            ans[id] = (road[id].first==u)?1:2;
        }
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n>>m;
    for(int i=1;i<=n;i++) dsu[i]=i;

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

    for(int i=1;i<=n;i++)
        if(!disc[i]) dfs(i,0);

    for(int i=1;i<=m;i++)
        if(!bridge[i]) merg(road[i].first, road[i].second);

    for(int i=1;i<=n;i++) adj[i].clear();

    for(int i=1;i<=m;i++)
        if(bridge[i]){
            int a=fin(road[i].first), b=fin(road[i].second);
            adj[a].push_back({b,i});
            adj[b].push_back({a,i});
        }

    int q; cin>>q;
    while(q--){
        int a,b; cin>>a>>b;
        val[fin(a)]++; val[fin(b)]--;
    }

    for(int i=1;i<=n;i++)
        if(fin(i)==i && !vis[i])
            dfs2(i,0);

    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: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40