oj.uz

Submission #321026

# Submission time Handle Problem Language Result Execution time Memory
321026 2020-11-10T16:55:24 Z hoangtung_pro One-Way Streets (CEOI17_oneway) C++14
100 / 100
 258 ms 24420 KB 
#include<bits/stdc++.h>

#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define bit(s, i) (s & (1<<i))

using namespace std;

const int N = 1e5 + 5;
const int M = 1;
const int K = 1;
const int mod = 1e9+7;
const int inf = 2e9;
const long long Inf = 2e18;

typedef long long ll;
typedef pair < int, int > ii;

int n, m, k, a[N], b[N];

vector < ii > adj[N];

int cnt = 0, num[N], low[N], h[N], p[N][20], pred[N], par[N], res[N];
bool brid[N];

void dfs(int u) {
    num[u] = low[u] = ++ cnt;
    int v, i;
    for(ii x : adj[u]) {
        tie(v, i) = x;
        if(num[v]) {
            if(p[v][0] == u) brid[v] = 0;
            if(v != p[u][0]) low[u] = min(low[u], low[v]);
        }
        else {
            h[v] = h[u] + 1, p[v][0] = u, pred[v] = i;
            dfs(v);
            low[u] = min(low[u], low[v]);
            if(low[v] > num[u]) brid[v] = 1;
        }
    }
}

int LCA(int u, int v)
{
    if(h[u] > h[v]) swap(u, v);

    for(int i=18;i>=0;--i) if( h[p[v][i]] >= h[u] ) v = p[v][i];

    if(u == v) return u;

    for(int i=18;i>=0;--i)
    {
        if( p[u][i] != p[v][i] )
        {
            u = p[u][i];
            v = p[v][i];
        }
    }
    return p[u][0];
}

int get(int x) {
    if(x == par[x]) return x;
    return par[x] = get(par[x]);
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // freopen("trash.inp","r",stdin);
    // freopen("trash.out","w",stdout);

    cin >> n >> m;
    for(int i=1;i<=m;++i) {
        cin >> a[i] >> b[i];
        adj[a[i]].pb({b[i], i});
        adj[b[i]].pb({a[i], i});
    }

    for(int i=1;i<=n;++i) if(!num[i]) dfs(i);

    for(int j=1;j<=18;++j)
    for(int i=1;i<=n;++i)  if((1<<j) <= h[i]) p[i][j] = p[p[i][j-1]][j-1];

    for(int i=1;i<=n;++i) par[i] = i;

    cin >> k;
    while(k --) {
        int u, v, pa;
        cin >> u >> v;
        pa = LCA(u, v);

        u = get(u);
        while(h[u] > h[pa]) {
            if(brid[u]) res[pred[u]] = -1;
            par[u] = p[u][0];
            u = get(u);
        }

        v = get(v);
        while(h[v] > h[pa]) {
            if(brid[v]) res[pred[v]] = 1;
            par[v] = p[v][0];
            v = get(v);
        }
    }

    for(int i=1;i<=n;++i) if(brid[i] && b[pred[i]] != i) {
        res[pred[i]] *= -1;
    }

    for(int i=1;i<=m;++i) {
        if(!res[i]) cout << "B";
        if(res[i] == 1) cout << "R";
        if(res[i] == -1) cout << "L";
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2796 KB Output is correct
3 Correct 2 ms 2924 KB Output is correct
4 Correct 2 ms 2924 KB Output is correct
5 Correct 3 ms 2924 KB Output is correct
6 Correct 3 ms 2796 KB Output is correct
7 Correct 2 ms 2924 KB Output is correct
8 Correct 3 ms 2924 KB Output is correct
9 Correct 3 ms 2796 KB Output is correct
10 Correct 2 ms 2796 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2796 KB Output is correct
3 Correct 2 ms 2924 KB Output is correct
4 Correct 2 ms 2924 KB Output is correct
5 Correct 3 ms 2924 KB Output is correct
6 Correct 3 ms 2796 KB Output is correct
7 Correct 2 ms 2924 KB Output is correct
8 Correct 3 ms 2924 KB Output is correct
9 Correct 3 ms 2796 KB Output is correct
10 Correct 2 ms 2796 KB Output is correct
11 Correct 47 ms 10468 KB Output is correct
12 Correct 55 ms 12640 KB Output is correct
13 Correct 72 ms 15644 KB Output is correct
14 Correct 86 ms 18792 KB Output is correct
15 Correct 88 ms 19684 KB Output is correct
16 Correct 77 ms 18808 KB Output is correct
17 Correct 82 ms 20344 KB Output is correct
18 Correct 80 ms 18788 KB Output is correct
19 Correct 91 ms 21348 KB Output is correct
20 Correct 56 ms 13796 KB Output is correct
21 Correct 54 ms 13796 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2796 KB Output is correct
3 Correct 2 ms 2924 KB Output is correct
4 Correct 2 ms 2924 KB Output is correct
5 Correct 3 ms 2924 KB Output is correct
6 Correct 3 ms 2796 KB Output is correct
7 Correct 2 ms 2924 KB Output is correct
8 Correct 3 ms 2924 KB Output is correct
9 Correct 3 ms 2796 KB Output is correct
10 Correct 2 ms 2796 KB Output is correct
11 Correct 47 ms 10468 KB Output is correct
12 Correct 55 ms 12640 KB Output is correct
13 Correct 72 ms 15644 KB Output is correct
14 Correct 86 ms 18792 KB Output is correct
15 Correct 88 ms 19684 KB Output is correct
16 Correct 77 ms 18808 KB Output is correct
17 Correct 82 ms 20344 KB Output is correct
18 Correct 80 ms 18788 KB Output is correct
19 Correct 91 ms 21348 KB Output is correct
20 Correct 56 ms 13796 KB Output is correct
21 Correct 54 ms 13796 KB Output is correct
22 Correct 258 ms 21476 KB Output is correct
23 Correct 197 ms 19940 KB Output is correct
24 Correct 170 ms 20068 KB Output is correct
25 Correct 237 ms 24420 KB Output is correct
26 Correct 207 ms 21112 KB Output is correct
27 Correct 168 ms 19940 KB Output is correct
28 Correct 50 ms 6884 KB Output is correct
29 Correct 129 ms 14436 KB Output is correct
30 Correct 139 ms 14820 KB Output is correct
31 Correct 143 ms 14948 KB Output is correct
32 Correct 161 ms 18404 KB Output is correct