oj.uz

Submission #89981

# Submission time Handle Problem Language Result Execution time Memory
89981 2018-12-19T12:53:02 Z mra2322001 One-Way Streets (CEOI17_oneway) C++14
0 / 100
 6 ms 2296 KB 
#include <bits/stdc++.h>
#define f0(i, n) for(int i(0); i < (n); i++)
#define f1(i, n) for(int i(1); i <= n; i++)
#define u first
#define v second

using namespace std;
typedef long long ll;
const int N = 100002;

int n, m, P;
map <pair <int, int>, int> g;
pair <int, int> ed[N];
vector <vector <int> > a;
/// cau
int num[N], low[N], cnt = 0;
/// disjoin set
int parent[N];
/// canh trong do thi moi
pair <int, int> newed[N];
/// dinh, canh trong do thi moi
int newdinh, newcanh;
/// dinh u thuoc dinh moi nao
int in[N];
/// lca
int f[N][17], h[N];
/// cung noi
int e1[N], e2[N];
map <pair <int, int>, char> Q;
map <pair <int, int>, int> cau;

int getroot(int u){
    if(parent[u]==0) return u;
    parent[u] = getroot(parent[u]);
    return parent[u];
}

void join(int u, int v){
    parent[getroot(v)] = getroot(u);
}

void dfs(int u, int p){
    num[u] = low[u] = ++cnt;
    for(auto v:a[u]){
        if(v==p) continue;
        if(num[v]) low[u] = min(low[u], num[v]);
        else{
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if(g[{u, v}]==1 && low[v] > num[u]){
                newed[++newcanh] = {getroot(u), getroot(v)};
                cau[{u, v}] = cau[{v, u}] = 1;
            }
            else{
                join(u, v);
            }
        }
    }
}

void timcau(){
    f1(i, n){
        if(num[i]==0) dfs(i, i);
    }
    map <int, int> thuoc; /// dinh u thuoc cha nao
    f1(i, n){
        int p = getroot(i);
        if(thuoc[p]==0) thuoc[p] = ++newdinh;
        in[i] = thuoc[p];
    }
    /// clear lai do thi cu
    f1(i, n) a[i].clear();
    f1(i, newcanh){
        int u = newed[i].u, v = newed[i].v;
        a[in[u]].emplace_back(in[v]);
        a[in[v]].emplace_back(in[u]);
    }
}

void dfs2(int u){
    num[u] = 1;
    for(auto v:a[u]){
        if(num[v]) continue;
        f[v][0] = u;
        h[v] = h[u] + 1;
        dfs2(v);
    }

}

int lca(int u, int v){
    if(h[u] < h[v]) swap(u, v);
    for(int k = 16; k >= 0; k--){
        if(h[u] - (1ll << k) >= h[v]) u = f[u][k];
    }
    if(u==v) return 1;
    for(int k = 16; k >= 0; k--){
        if(f[u][k] > 0 && f[v][k] > 0 && f[u][k] != f[v][k])
            u = f[u][k], v = f[v][k];
    }
    return f[u][0];
}

void buildlca(){
    /// dung lai ham num
    f1(i, newdinh) num[i] = 0;
    f1(i, newdinh){
        if(num[i]==0){
            dfs2(i);
        }
    }
    f1(i, 16) f1(u, newdinh) f[u][i] = f[f[u][i - 1]][i - 1];
    memset(e1, 0x3f3f3f, sizeof(e1));
    memset(e2, 0x3f3f3f, sizeof(e2));
}

void add1(int u, int v){
    /// noi u vao v
    e1[u] = min(e1[u], h[v]);
}

void add2(int u, int v){
    e2[u] = min(e2[u], h[v]);
}

void dfs3(int u){
    num[u] = 1;
    for(auto v:a[u]){
        if(num[v]) continue;
        dfs3(v);
        if(e1[v] <= h[u]){
            Q[{u, v}] = Q[{v, u}] = 'R';
        }
        e1[u] = min(e1[u], e1[v]);
    }
}

void dfs4(int u){
    num[u] = 1;
    for(auto v:a[u]){
        if(num[v]) continue;
        dfs4(v);
        if(e2[v] <= h[u]){
            Q[{u, v}] = Q[{v, u}] = 'L';
        }
        e2[u] = min(e2[u], e2[v]);
    }
}

void build(){
    /// danh dau cac cung
    memset(num, 0, sizeof(num));
    f1(i, newdinh){
        if(num[i]==0){
            dfs3(i);
        }
    }
    memset(num, 0, sizeof(num));
    f1(i, newdinh){
        if(num[i]==0){
            dfs4(i);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    
    cin >> n >> m;
    a.resize(n + 1);
    f1(i, m){
        int u, v; cin >> u >> v;
        ed[i] = {u, v};
        a[u].emplace_back(v);
        a[v].emplace_back(u);
        g[{u, v}]++; g[{v, u}]++;
    }
    cin >> P;
    timcau();
    buildlca();
    while(P--){
        int u, v; cin >> u >> v;
        /// u phai den v
        int x = lca(in[u], in[v]);
        if(x==in[v]){
            add1(in[u], x);
            continue;
        }
        if(x==in[u]){
            add2(in[v], x);
            continue;
        }
        add1(in[u], x);
        add2(in[v], x);
    }
    build();
    f1(i, m){
        int u = ed[i].u, v = ed[i].v;
        if(cau[{u, v}]){
            if(Q.find({in[u], in[v]}) != Q.end()){
                char c = Q[{in[u], in[v]}];
                if(c=='R'){
                    /// di xuong
                    if(h[in[u]] < h[in[v]]) c = 'L';
                    else c = 'R';
                }
                else{
                    if(h[in[u]] > h[in[v]]) c = 'L';
                    else c = 'R';
                }
                cout << c;
            }
            else cout << "B";
        }
        else cout << "B";
    }
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 3 ms 1660 KB Output is correct
3 Correct 5 ms 2000 KB Output is correct
4 Correct 6 ms 2176 KB Output is correct
5 Incorrect 6 ms 2296 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 3 ms 1660 KB Output is correct
3 Correct 5 ms 2000 KB Output is correct
4 Correct 6 ms 2176 KB Output is correct
5 Incorrect 6 ms 2296 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 3 ms 1660 KB Output is correct
3 Correct 5 ms 2000 KB Output is correct
4 Correct 6 ms 2176 KB Output is correct
5 Incorrect 6 ms 2296 KB Output isn't correct
6 Halted 0 ms 0 KB -