oj.uz

Submission #904032

# Submission time Handle Problem Language Result Execution time Memory
904032 2024-01-11T18:05:45 Z Dec0Dedd One-Way Streets (CEOI17_oneway) C++14
0 / 100
 6 ms 20700 KB 
#include <bits/stdc++.h>

using namespace std;

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

const int N = 1e5+10;
const int K = 20;

vector<int> G[N];
set<int> T[N];
int n, m, p, x[N], y[N], a[N], b[N], tin[N], tout[N], low[N], rt[N], t;
pii prf[N];
int up[K][N];
bool vis[N];
map<pii, bool> brg;
map<pii, int> eds;
vector<int> vcs[N];

void brd(int v, int p) {
    vis[v]=true;
    tin[v]=low[v]=t++;

    for (auto u : G[v]) {
        if (u == p) continue;
        if (vis[u]) low[v]=min(low[v], tin[u]);
        else {
            brd(u, v);
            low[v]=min(low[v], low[u]);
            if (low[u] > tin[v]) brg[{u, v}]=brg[{v, u}]=true;
        }
    }
}

void gen(int v, int r) {
    vis[v]=true;

    rt[v]=r;
    vcs[r].push_back(v);
    for (auto u : G[v]) {
        if (vis[u]) continue;
        if (brg[{v, u}]) gen(u, u);
        else gen(u, r);
    }
}

void dfs(int v, int p) {
    up[0][v]=p;
    for (int i=1; i<K; ++i) up[i][v]=up[i-1][up[i-1][v]];

    tin[v]=++t;
    for (auto u : T[v]) {
        if (u == p) continue;
        dfs(u, v);
    } tout[v]=t;
}

bool anc(int v, int u) {
    return tin[v] <= tin[u] && tout[u] <= tout[v];
}

int lca(int v, int u) {
    if (anc(v, u)) return v;
    if (anc(u, v)) return u;

    for (int i=K-1; i>=0; --i) {
        if (!anc(up[i][v], u)) v=up[i][v];
    } return up[0][v];
}

pii mrg(pii a, pii b) {
    return {a.first+b.first, a.second+b.second};
}

void repl(int v, int p) {
    for (auto u : T[v]) {
        if (u == p) continue;
        repl(u, v);
        prf[v]=mrg(prf[v], prf[u]);
    }
}

void solve() {
    cin>>n>>m;
    for (int i=1; i<=m; ++i) {
        cin>>a[i]>>b[i];
        G[a[i]].push_back(b[i]);
        G[b[i]].push_back(a[i]);
        ++eds[{a[i], b[i]}];
    }

    for (int i=1; i<=n; ++i) {
        if (vis[i]) continue;
        brd(i, i);
    } memset(vis, false, sizeof(vis));

    for (int i=1; i<=m; ++i) {
        if (eds[{a[i], b[i]}] > 1 || eds[{b[i], a[i]}]) brg[{a[i], b[i]}]=false;
    }

    for (int i=1; i<=n; ++i) {
        if (vis[i]) continue;
        gen(i, i);
    }

    for (int i=1; i<=n; ++i) {
        if (rt[i] != i) continue;
        for (auto v : vcs[i]) {
            for (auto u : G[v]) {
                if (rt[u] == rt[v]) continue;
                T[i].insert(rt[u]);
            }
        }
    }

    memset(vis, false, sizeof(vis));
    memset(tin, false, sizeof(tin));
    memset(low, false, sizeof(low));
    t=0;

    vector<int> vx;
    for (int i=1; i<=n; ++i) {
        if (rt[i] != i) continue;
        if (tin[i]) continue;
        dfs(i, i), vx.push_back(i);
    }

    cin>>p;
    for (int i=1; i<=p; ++i) {
        cin>>x[i]>>y[i];
        x[i]=rt[x[i]], y[i]=rt[y[i]];
        int l=lca(x[i], y[i]);
        ++prf[x[i]].first;
        ++prf[y[i]].second;
        --prf[l].first, --prf[l].second;

    }

    for (auto u : vx) repl(u, u);
    for (int i=1; i<=m; ++i) {
        int ra=rt[a[i]], rb=rt[b[i]];
        if (ra == rb) cout<<"B";
        else {
            if (anc(ra, rb)) { // a is anc
                assert(!(prf[rb].first > 0 && prf[rb].second > 0));
                if (prf[rb].first > 0) {
                    // go towards ancestor b -> a
                    cout<<"L";
                } else if (prf[rb].second > 0) {
                    // go towards son a -> b
                    cout<<"R";  
                } else cout<<"B";
            } else {
                assert(!(prf[ra].first > 0 && prf[ra].second > 0));
                if (prf[ra].first > 0) {
                    // go towards ancestor a -> b
                    cout<<"R";
                } else if (prf[ra].second > 0) {
                    cout<<"L";
                } else cout<<"B";
            }
        }
    } cout<<"\n";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int t=1;
    while (t--) solve();
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20060 KB Output is correct
2 Correct 5 ms 20216 KB Output is correct
3 Correct 5 ms 20320 KB Output is correct
4 Correct 5 ms 20568 KB Output is correct
5 Correct 6 ms 20572 KB Output is correct
6 Correct 4 ms 20312 KB Output is correct
7 Correct 5 ms 20572 KB Output is correct
8 Correct 5 ms 20700 KB Output is correct
9 Correct 4 ms 20316 KB Output is correct
10 Incorrect 5 ms 20312 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20060 KB Output is correct
2 Correct 5 ms 20216 KB Output is correct
3 Correct 5 ms 20320 KB Output is correct
4 Correct 5 ms 20568 KB Output is correct
5 Correct 6 ms 20572 KB Output is correct
6 Correct 4 ms 20312 KB Output is correct
7 Correct 5 ms 20572 KB Output is correct
8 Correct 5 ms 20700 KB Output is correct
9 Correct 4 ms 20316 KB Output is correct
10 Incorrect 5 ms 20312 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20060 KB Output is correct
2 Correct 5 ms 20216 KB Output is correct
3 Correct 5 ms 20320 KB Output is correct
4 Correct 5 ms 20568 KB Output is correct
5 Correct 6 ms 20572 KB Output is correct
6 Correct 4 ms 20312 KB Output is correct
7 Correct 5 ms 20572 KB Output is correct
8 Correct 5 ms 20700 KB Output is correct
9 Correct 4 ms 20316 KB Output is correct
10 Incorrect 5 ms 20312 KB Output isn't correct
11 Halted 0 ms 0 KB -