제출 #1259075

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

oneway

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;

using ll = long long;
using ii = pair<int,int>;
using pii = pair<int,ii>;
using aa = array<int,5>;

const int N = 1e5+5;
const int MAX = 100;
const int INF = 1e9;
const int MOD = 998244353;

int n,m,u,v,q,cnt = 0,timer = 0;
int num[N],low[N],scc[N],pre[N];
ii p[N];
bool vis[N];
stack<int> st;
vector <ii> adj[N];
vector <int> g[N];
map<ii,int> mp;

void dfs(int u,int p){
    num[u] = low[u] = ++timer;
    st.push(u);
    for(ii it : adj[u]){
        int v = it.fi;
        if (it.se == p) continue;
        if (!num[v]){
            dfs(v,it.se);
            low[u] = min(low[u],low[v]);
        } else low[u] = min(low[u],num[v]);
    }
    if (low[u] == num[u]){
        int v = -1;
        cnt++;
        while (v != u){
            v = st.top();
            scc[v] = cnt;
            st.pop();
        }
    }
}
void dp(int u,int p){
    vis[u] = 1;
    for (int it : g[u]){
        if (vis[it]) continue;
        dp(it,u);
        pre[u] += pre[it];
    }
    if (pre[u] > 0) mp[{u,p}] = 1;
    else if (pre[u] < 0) mp[{p,u}] = 1;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
//    freopen("main.in","r",stdin);
//    freopen("main.out","w",stdout);
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        cin >> u >> v;
        p[i] = {u,v};
        adj[u].push_back({v,i});
        adj[v].push_back({u,i});
    }
    for (int i = 1; i <= n; i++){
        if (!num[i]) dfs(i,0);
    }
    for (int i = 1; i <= n; i++){
        for (ii x : adj[i]){
            if (scc[i] == scc[x.fi]) continue;
            g[scc[i]].push_back(scc[x.fi]);
        }
    }
    cin >> q;
    for (int i = 1; i <= q; i++){
        cin >> u >> v;
        pre[scc[u]]++;
        pre[scc[v]]--;
    }
    for (int i = 1; i <= cnt; i++){
        if (!vis[i]) dp(i,0);
    }
    for (int i = 1; i <= m; i++){
        tie(u,v) = p[i];
        u = scc[u];
        v == scc[v];
        if (u == v){
            cout << "B";
            continue;
        }
        cout << (mp[{u,v}] ? "R" : mp[{v,u}] ? "L" : "B");
    }
    return 0;
}

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