oj.uz

Submission #904045

# Submission time Handle Problem Language Result Execution time Memory
904045 2024-01-11T18:32:51 Z Dec0Dedd One-Way Streets (CEOI17_oneway) C++14
100 / 100
 530 ms 71252 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]}]=brg[{b[i], a[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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20060 KB Output is correct
2 Correct 3 ms 20060 KB Output is correct
3 Correct 5 ms 20316 KB Output is correct
4 Correct 5 ms 20724 KB Output is correct
5 Correct 5 ms 20672 KB Output is correct
6 Correct 5 ms 20328 KB Output is correct
7 Correct 5 ms 20584 KB Output is correct
8 Correct 7 ms 20584 KB Output is correct
9 Correct 5 ms 20420 KB Output is correct
10 Correct 5 ms 20328 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20060 KB Output is correct
2 Correct 3 ms 20060 KB Output is correct
3 Correct 5 ms 20316 KB Output is correct
4 Correct 5 ms 20724 KB Output is correct
5 Correct 5 ms 20672 KB Output is correct
6 Correct 5 ms 20328 KB Output is correct
7 Correct 5 ms 20584 KB Output is correct
8 Correct 7 ms 20584 KB Output is correct
9 Correct 5 ms 20420 KB Output is correct
10 Correct 5 ms 20328 KB Output is correct
11 Correct 175 ms 38664 KB Output is correct
12 Correct 193 ms 40592 KB Output is correct
13 Correct 200 ms 43948 KB Output is correct
14 Correct 341 ms 49656 KB Output is correct
15 Correct 368 ms 51664 KB Output is correct
16 Correct 498 ms 63644 KB Output is correct
17 Correct 377 ms 65936 KB Output is correct
18 Correct 485 ms 63568 KB Output is correct
19 Correct 414 ms 67648 KB Output is correct
20 Correct 189 ms 41152 KB Output is correct
21 Correct 148 ms 41164 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20060 KB Output is correct
2 Correct 3 ms 20060 KB Output is correct
3 Correct 5 ms 20316 KB Output is correct
4 Correct 5 ms 20724 KB Output is correct
5 Correct 5 ms 20672 KB Output is correct
6 Correct 5 ms 20328 KB Output is correct
7 Correct 5 ms 20584 KB Output is correct
8 Correct 7 ms 20584 KB Output is correct
9 Correct 5 ms 20420 KB Output is correct
10 Correct 5 ms 20328 KB Output is correct
11 Correct 175 ms 38664 KB Output is correct
12 Correct 193 ms 40592 KB Output is correct
13 Correct 200 ms 43948 KB Output is correct
14 Correct 341 ms 49656 KB Output is correct
15 Correct 368 ms 51664 KB Output is correct
16 Correct 498 ms 63644 KB Output is correct
17 Correct 377 ms 65936 KB Output is correct
18 Correct 485 ms 63568 KB Output is correct
19 Correct 414 ms 67648 KB Output is correct
20 Correct 189 ms 41152 KB Output is correct
21 Correct 148 ms 41164 KB Output is correct
22 Correct 507 ms 67084 KB Output is correct
23 Correct 444 ms 64916 KB Output is correct
24 Correct 524 ms 64724 KB Output is correct
25 Correct 450 ms 71252 KB Output is correct
26 Correct 460 ms 66492 KB Output is correct
27 Correct 530 ms 64948 KB Output is correct
28 Correct 95 ms 23636 KB Output is correct
29 Correct 209 ms 41856 KB Output is correct
30 Correct 178 ms 42320 KB Output is correct
31 Correct 197 ms 42404 KB Output is correct
32 Correct 312 ms 49488 KB Output is correct