oj.uz

Submission #595086

# Submission time Handle Problem Language Result Execution time Memory
595086 2022-07-13T11:02:44 Z OttoTheDino One-Way Streets (CEOI17_oneway) C++17
0 / 100
 2 ms 4948 KB 
#include <bits/stdc++.h>
using namespace std;

#define rep(i,s,e)                  for (int i = s; i <= e; ++i)
#define rrep(i,s,e)                 for (int i = s; i >= e; --i)
#define pb                          push_back
#define pf                          push_front
#define fi                          first
#define se                          second
#define all(a)                      a.begin(), a.end()
#define len(a)                      (int)a.size()
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;

const int mx = 1e5, C = 30;
vii adj[mx+1];
vi reach[mx+1];
int tp[mx+1], par[mx+1][C+1], dep[mx+1], cyc[mx+1], delta[mx+1], done[mx+1]; 
ii edg[mx+1];

int go_up (int x, int l) {
    rep (i,0,C) {
        if (l%2) x = par[x][i];
        l /= 2;
    }
    return x;
}

int lca (int a, int b) {
    if (dep[a]<dep[b]) swap(a,b);
    int dif = dep[a]-dep[b];
    a = go_up (a, dif);

    if (a==b) return a;

    rrep (i, C, 0) {
        if (par[a][i] != par[b][i]) {
            a = par[a][i];
            b = par[b][i];
        }
    }

    return par[a][0];
}


void dfs (int u) {
    for (ii ve : adj[u]) {
        int v = ve.fi;
        if (!par[v][0]) {
            dep[v] = dep[u]+1;
            par[v][0] = u;
            dfs (v);
        }
    }
}

ii dfs2 (int u, int le) {
    done[u] = 1;
    int c = 0, d = 0;
    for (ii ve : adj[u]) {
        int v = ve.fi, e = ve.se;

        if (e==le) continue;

        if (done[v]) {
            if (dep[v]<dep[u]) {
                c++;
                cyc[v]++;
            }
            continue;
        }

        ii res = dfs2 (v, e);
        if (!res.fi && res.se) {
            if ((res.se>0 && edg[e].fi!=u) || (res.se<0 && edg[e].fi==u)) tp[e] = 2;
            else tp[e] = 1;
        }
        c += res.fi;
        d += res.se;
    }

    c -= cyc[u];
    d -= delta[u];

    for (int v : reach[u]) {
        int p = lca(abs(v),u);
        if (p!=u) {
            d += 1-2*(v<0);
            delta[p] += 1-2*(v<0);
        }
    }

    return {c,d};
}

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

    int n, m; cin >> n >> m;

    rep (i,1,m) {
        int a, b; cin >> a >> b;
        adj[a].pb({b,i});
        adj[b].pb({a,i});
        edg[i] = {a,b};
    }

    int p; cin >> p;

    rep (i,1,p) {
        int x, y; cin >> x >> y;
        reach[x].pb(y);
        reach[y].pb(-x);
    }

    dep[1] = 1;
    par[1][0] = 1;
    dfs (1);

    rep (i,1,C)
        rep (j,1,n-(1<<C)+1)
            par[j][i] = par[par[j][i-1]][i-1];

    dfs2 (1,-1);

    rep (i,1,m) cout << "BLR"[tp[i]];
    cout << "\n";

    return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4948 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 4948 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 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -