oj.uz

Submission #503425

# Submission time Handle Problem Language Result Execution time Memory
503425 2022-01-07T23:30:33 Z Lobo One-Way Streets (CEOI17_oneway) C++17
0 / 100
 2 ms 2892 KB 
#include<bits/stdc++.h>
using namespace std;

const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 110000

int n, m, q;
int mark[maxn], p[maxn][23], span[maxn], h[maxn];
int low[maxn], ps[maxn];
vector<pair<int,int>> g[maxn];
pair<int,int> edg[maxn];

void dfstree(int u, int idant, int ant) {
    mark[u] = 1;
    p[u][0] = ant;
    for(int i = 1; i <= 20; i++) {
        p[u][i] = p[p[u][i-1]][i-1];
    }

    for(auto V : g[u]) {
        int v = V.fr;
        int id = V.sc;
        if(idant == id) continue;

        if(!mark[v]) {
            span[id] = 1;  
            h[v] = h[u]+1;
            dfstree(v,id,u); 
        }
    }
}

void dfslow(int u, int idant, int ant) {

    low[u] = inf;
    for(auto V : g[u]) {
        int v = V.fr;
        int id = V.sc;
        if(id == idant) continue;

        if(span[id]) {
            dfslow(v,id,u);
        }
        else {
            if(h[v] < h[u]) low[u] = min(low[u],h[v]);
        }

    }
}

void dfsps(int u, int ant) {

    for(auto V : g[u]) {
        int v = V.fr;
        int id = V.sc;
        if(v == ant || !span[id]) continue;

        dfsps(v,u);
        ps[u]+= ps[v];
    }
}

int lca(int u, int v) {
    if(h[u] < h[v]) swap(u,v);

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

    if(u == v) {
        return u;
    }

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

    return p[u][0];
}

void solve() {
    cin >> n >> m;

    for(int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].pb(mp(v,i));
        g[v].pb(mp(u,i));
        edg[i] = mp(u,v);
    }

    dfstree(1,0,1);
    dfslow(1,0,1);


    cin >> q;
    for(int i = 1; i <= q; i++) {
        int u, v;
        cin >> u >> v;
        int lc = lca(u,v);

        ps[u]++;
        ps[v]--;
    }

    dfsps(1,1);

    for(int i = 1; i <= m; i++) {
        if(edg[i].fr == edg[i].sc) {
            cout << 'B';
            continue;
        }
        int ans = 1;

        int u = edg[i].fr;
        int v = edg[i].sc;

        if(p[u][0] == v) {swap(u,v); ans*= -1;}
        //u e pai de v

        ans*= ps[v];

        if(low[v] <= h[u] || !span[i]) {
            cout << 'B';
        }
        else {
            if(ans > 0) cout << 'L';
            else if(ans < 0) cout << 'R';
            else cout << 'B';
        }
    }


}

//encontrar todas as bridge edges com dfs tree
//caminho u->lc->v -- prefix sum ps[u]++, ps[v]-- -> dsfps
// + = subindo, - = descendo

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);

    int tt = 1;
    // cin >> tt;
    while(tt--) solve();
    return 0;

}

Compilation message

oneway.cpp: In function 'void solve()':
oneway.cpp:115:13: warning: unused variable 'lc' [-Wunused-variable]
  115 |         int lc = lca(u,v);
      |             ^~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2892 KB Output isn't correct
2 Halted 0 ms 0 KB -