제출 #934496

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

oneway

// In the name of the God
#include <bits/stdc++.h>
#define ll long long
// #define int long long
#define pb push_back
#define F first
#define S second
#define mp make_pair
#define pii pair <int, int>
#define smin(x, y) (x) = min((x), (y))
#define smax(x, y) (x) = max((x), (y))
#define all(x) (x).begin(), (x).end()
using namespace std;

const int inf = 1e9+7;
const int mod = 998244353;
const int maxn = 1e5+5;

int n, m, p, fr[maxn], to[maxn], x[maxn], y[maxn], dp[maxn], col[maxn], h[maxn];
bool mark[maxn], seen[maxn];
char ans[maxn];
vector <int> adj[maxn];
vector <pii> adj_[maxn];

int dfs1(int v, int id) {
    seen[v] = 1;
    int mnh = h[v];
    for (int e : adj[v]) {
        int u = fr[e]==v?to[e]:fr[e];
        if (seen[u]) {
            if (e != id) smin(mnh, h[u]);
        }
        else {
            h[u] = h[v]+1;
            int tmp = dfs1(u, e);
            if (tmp > h[v]) mark[e] = 1;
            smin(mnh, tmp);
        }
    }
    return mnh;
}

void dfs2(int v, int ali) {
    seen[v] = 1, col[v] = ali;
    for (int e : adj[v]) {
        int u = fr[e]==v?to[e]:fr[e];
        if (!seen[u] and !mark[e]) dfs2(u, ali);
    }
}


void dfs3(int v, int ed = -1) {
    seen[v] = 1;
    for (pii e : adj_[v]) {
        if (!seen[e.F]) {
            dfs3(e.F, e.S); dp[v] += dp[e.F];
        }
    }
    // cout << v << ' ' << dp[v] << ' ' << ed << '\n';
    if (ed != -1) {
        if (dp[v] == 0) ans[ed] = 'B';
        else if (dp[v] > 0) {
            // cout << "GGGO\n";
            if (col[fr[ed]] == v) ans[ed] = 'R';
            else ans[ed] = 'L';
        }
        else {
            // cout << "GGGO\n";
            if (col[fr[ed]] == v) ans[ed] = 'L';
            else ans[ed] = 'R';
        }
    }
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> fr[i] >> to[i]; fr[i]--, to[i]--;
        adj[fr[i]].pb(i);
        if (fr[i] != to[i]) adj[to[i]].pb(i);
    }
    cin >> p;
    for (int i = 0; i < p; i++) {
        cin >> x[i] >> y[i];
        x[i]--, y[i]--;
    }
    for (int i = 0; i < n; i++) {
        if (!seen[i]) dfs1(i, -1);
    }
    fill(seen, seen+n, 0);
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (!seen[i]) dfs2(i, cnt++);
    }
    // cout << cnt << '\n';
    for (int i = 0; i < p; i++) {
        if (col[x[i]] != col[y[i]]) {
            // cout << "HI" << i << '\n';
            dp[col[x[i]]]++, dp[col[y[i]]]--;
        }
    }
    for (int i = 0; i < m; i++) {
        if (mark[i]) {
            adj_[col[fr[i]]].pb(mp(col[to[i]], i));
            adj_[col[to[i]]].pb(mp(col[fr[i]], i));
        }
    }
    fill(seen, seen+n, 0);
    for (int i = 0; i < cnt; i++) {
        if (!seen[i]) dfs3(i);
    }
    for (int i = 0; i < m; i++) {
        if (!mark[i]) cout << 'B';
        else cout << ans[i];
    }
    cout << '\n';
    return 0;
}

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