oj.uz

답안 #321774

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
321774 2020-11-13T10:55:08 Z Karen124 One-Way Streets (CEOI17_oneway) C++14
0 / 100
 2 ms 2668 KB 
#include <bits/stdc++.h>
     
using namespace std;
     
#define ll long long int 
#define F first
#define S second
#define pb push_back
 
const ll N = 1e5 + 10;
const ll LOG = 20;
const ll MOD = 1e9 + 7;
const ll INF = 1e9 + 10;
struct Edge{
    int u, v;
} e[N];
int n, m, p, a[N], b[N];
int h[N], mn[N];
int pr[N], sz[N];
int rev[N], ps[N];
vector < pair <int, int> > adj[N];
vector <int>  E;
bool mrk[N], is[N];
void dfs(int v, int i){
    mrk[v] = 1; mn[v] = h[v];
    for (auto it : adj[v]){
        int u = it.F, j = it.S;
        if (!mrk[u]){
            h[u] = h[v] + 1;
            dfs(u, j);
            mn[v] = min(mn[u], mn[v]);
        }
        else if (i != j){
            mn[v] = min(mn[v], h[u]);   
        }
    }
    if(i && mn[v] == h[v]){
        E.pb(i);
        is[i] = 1;
    }
    return;
}
int find(int v){
    if (pr[v] == v) return v;
    return (pr[v] = find(pr[v]));
}
void merge(int u, int v){
    u = find(u); v = find(v);
    if (u == v) return;
    if (sz[v] < sz[u]) swap(u, v);
    pr[u] = v;
    sz[v] += sz[u];
    return;
}
void dfs_dead(int v, int i){
    mrk[v] = 1;
    for (auto it : adj[v]){
        int u = it.F, j = it.S;
        if (mrk[u]) continue;
        dfs_dead(u, j);
        ps[v] += ps[u];
    }
    if (i && ps[v]){
        rev[i] = 1;
        rev[i] += (0 < ps[v] && find(e[i].u) == v);    
        rev[i] += (ps[v] < 0 && find(e[i].v) == v);
    }
    return;
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        cin >> e[i].u >> e[i].v;
        adj[e[i].u].pb({e[i].v, i});
        adj[e[i].v].pb({e[i].u, i});
    }
    for (int i = 1; i <= n; i++){
        if (!mrk[i]){
            dfs(i, 0);
        }
        sz[i] = 1; pr[i] = i;
    }
    cin >> p;
    for (int i = 1; i <= p; i++){
        cin >> a[i] >> b[i];
    }
    for (int i = 1; i <= m; i++){
        if (!is[i]){
            merge(e[i].u, e[i].v);
        }
    }
    for (int i = 1; i <= n; i++) adj[i].clear();
    for (int i : E){
        adj[find(e[i].u)].pb({find(e[i].v), i});
        adj[find(e[i].v)].pb({find(e[i].u), i});
    }
    for (int i = 1; i <= p; i++){
        if (find(a[i]) == find(b[i])) continue;
        ps[a[i]]--; ps[b[i]]++; 
    }
    fill(mrk, mrk + n + 1, 0);
    for (int i = 1; i <= n; i++){
        if (!mrk[find(i)]){
            dfs_dead(find(i), 0);
        }
    }
    for (int i = 1; i <= m; i++){
        if (rev[i] == 1) cout << "R";
        else if (rev[i] == 2) cout << "L";
        else cout << "B";
    }
    cout << '\n';
    return 0;
}
/*
5 6
1 2
1 2
4 3
2 3
1 3
5 1
2
4 5
1 3
*/

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2668 KB Output isn't correct
2 Halted 0 ms 0 KB -