제출 #348532

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
348532		Mahdi_Shokoufi	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	120 ms	27360 KiB

oneway

//In The Name of Allah
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair < int , int > pii;
typedef pair < ll , ll > pll;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define Sz(x) (int)(x.size())

const int N = 1e5 + 10;
const ll mod = 1e9 + 7;
const int inf = 1e9 + 10;

int ea[N], eb[N], mark[N], h[N], dp[N], par[N], sz[N], sum[N];
vector < pii > adj[N], Adj[N];
vector < pair < pii , int > > fut;
char ans[N];

int getPar(int v){
    return par[v] == v ? v : par[v] = getPar(par[v]);
}

void merge(int u, int v){
    u = getPar(u);
    v = getPar(v);
    if (u == v)
        return;
    if (sz[v] < sz[u])
        swap(u, v);
    par[u] = v;
    sz[v] += sz[u];
}

void cutDFS(int v, int p){
    mark[v] = 1;
    dp[v] = inf;
    for (pii e : adj[v]){
        int u = e.X, id = e.Y;
        if (id == p)
            continue;
        if (mark[u]){
            merge(u, v);
            ans[id] = 'B';
            dp[v] = min(dp[v], h[u]);
        }
        else{
            h[u] = h[v] + 1;
            cutDFS(u, id);
            dp[v] = min(dp[v], dp[u]);
            if (h[v] < dp[u]){
                fut.pb(mp(mp(u, v), id));
            }
            else{
                merge(u, v);
                ans[id] = 'B';
            }
        }
    }
}

void calDFS(int v){
    mark[v] = 1;
    for (pii e : Adj[v]){
        int u = e.X, id = e.Y;
        if (mark[u])
            continue;
        calDFS(u);
        sum[v] += sum[u];
        if (sum[u] == 0){
            ans[id] = 'B';
        }
        if (sum[u] > 0){
            if (getPar(ea[id]) == u)
                ans[id] = 'R';
            else
                ans[id] = 'L';
        }
        if (sum[u] < 0){
            if (getPar(ea[id]) == v)
                ans[id] = 'R';
            else
                ans[id] = 'L';
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i ++){
        cin >> ea[i] >> eb[i];
        adj[ea[i]].pb(mp(eb[i], i));
        adj[eb[i]].pb(mp(ea[i], i));
    }
    for (int i = 0; i < N; i ++)
        par[i] = i, sz[i] = 1;
    for (int i = 1; i <= n; i ++){
        if (!mark[i])
            cutDFS(i, -1);
    }
    for (auto x : fut){
        int u = x.X.X;
        int v = x.X.Y;
        int id = x.Y;
        u = getPar(u);
        v = getPar(v);
        Adj[u].pb(mp(v, id));
        Adj[v].pb(mp(u, id));
    }
    memset(mark, 0, sizeof mark);
    int q;
    cin >> q;
    for (int i = 0; i < q; i ++){
        int x, y;
        cin >> x >> y;
        x = getPar(x);
        y = getPar(y);
        sum[x] ++;
        sum[y] --;
    }
    for (int i = 1; i <= n; i ++)
        if (!mark[i])
            calDFS(i);
    for (int i = 0; i < m; i ++)
        cout << ans[i];
    return 0;
}

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