oj.uz

Submission #348532

# Submission time Handle Problem Language Result Execution time Memory
348532 2021-01-15T06:30:52 Z Mahdi_Shokoufi One-Way Streets (CEOI17_oneway) C++17
100 / 100
 120 ms 27360 KB 
//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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6252 KB Output is correct
2 Correct 5 ms 6252 KB Output is correct
3 Correct 5 ms 6380 KB Output is correct
4 Correct 5 ms 6508 KB Output is correct
5 Correct 5 ms 6380 KB Output is correct
6 Correct 5 ms 6508 KB Output is correct
7 Correct 5 ms 6380 KB Output is correct
8 Correct 5 ms 6380 KB Output is correct
9 Correct 5 ms 6252 KB Output is correct
10 Correct 5 ms 6252 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6252 KB Output is correct
2 Correct 5 ms 6252 KB Output is correct
3 Correct 5 ms 6380 KB Output is correct
4 Correct 5 ms 6508 KB Output is correct
5 Correct 5 ms 6380 KB Output is correct
6 Correct 5 ms 6508 KB Output is correct
7 Correct 5 ms 6380 KB Output is correct
8 Correct 5 ms 6380 KB Output is correct
9 Correct 5 ms 6252 KB Output is correct
10 Correct 5 ms 6252 KB Output is correct
11 Correct 49 ms 13292 KB Output is correct
12 Correct 62 ms 14700 KB Output is correct
13 Correct 66 ms 16364 KB Output is correct
14 Correct 80 ms 17768 KB Output is correct
15 Correct 91 ms 18288 KB Output is correct
16 Correct 92 ms 18144 KB Output is correct
17 Correct 85 ms 20856 KB Output is correct
18 Correct 91 ms 18144 KB Output is correct
19 Correct 83 ms 22880 KB Output is correct
20 Correct 53 ms 13804 KB Output is correct
21 Correct 50 ms 13548 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6252 KB Output is correct
2 Correct 5 ms 6252 KB Output is correct
3 Correct 5 ms 6380 KB Output is correct
4 Correct 5 ms 6508 KB Output is correct
5 Correct 5 ms 6380 KB Output is correct
6 Correct 5 ms 6508 KB Output is correct
7 Correct 5 ms 6380 KB Output is correct
8 Correct 5 ms 6380 KB Output is correct
9 Correct 5 ms 6252 KB Output is correct
10 Correct 5 ms 6252 KB Output is correct
11 Correct 49 ms 13292 KB Output is correct
12 Correct 62 ms 14700 KB Output is correct
13 Correct 66 ms 16364 KB Output is correct
14 Correct 80 ms 17768 KB Output is correct
15 Correct 91 ms 18288 KB Output is correct
16 Correct 92 ms 18144 KB Output is correct
17 Correct 85 ms 20856 KB Output is correct
18 Correct 91 ms 18144 KB Output is correct
19 Correct 83 ms 22880 KB Output is correct
20 Correct 53 ms 13804 KB Output is correct
21 Correct 50 ms 13548 KB Output is correct
22 Correct 110 ms 21984 KB Output is correct
23 Correct 110 ms 19172 KB Output is correct
24 Correct 120 ms 19428 KB Output is correct
25 Correct 109 ms 27360 KB Output is correct
26 Correct 105 ms 21472 KB Output is correct
27 Correct 105 ms 19552 KB Output is correct
28 Correct 41 ms 10476 KB Output is correct
29 Correct 71 ms 14316 KB Output is correct
30 Correct 70 ms 14700 KB Output is correct
31 Correct 73 ms 15084 KB Output is correct
32 Correct 81 ms 19688 KB Output is correct