oj.uz

Submission #595175

# Submission time Handle Problem Language Result Execution time Memory
595175 2022-07-13T12:17:20 Z OttoTheDino One-Way Streets (CEOI17_oneway) C++17
100 / 100
 295 ms 33784 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;

    rep (i,1,n) {
        if (!par[i][0]) {
            par[i][0] = i;
            dfs (i);
        }
    }

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

    rep (i,1,n) {
        if (!done[i]){
        dfs2 (i,-1);
        }
    }

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

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5024 KB Output is correct
3 Correct 5 ms 5204 KB Output is correct
4 Correct 5 ms 5156 KB Output is correct
5 Correct 4 ms 5204 KB Output is correct
6 Correct 6 ms 5160 KB Output is correct
7 Correct 5 ms 5204 KB Output is correct
8 Correct 4 ms 5204 KB Output is correct
9 Correct 4 ms 5112 KB Output is correct
10 Correct 8 ms 5116 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5024 KB Output is correct
3 Correct 5 ms 5204 KB Output is correct
4 Correct 5 ms 5156 KB Output is correct
5 Correct 4 ms 5204 KB Output is correct
6 Correct 6 ms 5160 KB Output is correct
7 Correct 5 ms 5204 KB Output is correct
8 Correct 4 ms 5204 KB Output is correct
9 Correct 4 ms 5112 KB Output is correct
10 Correct 8 ms 5116 KB Output is correct
11 Correct 49 ms 13608 KB Output is correct
12 Correct 60 ms 16060 KB Output is correct
13 Correct 112 ms 19772 KB Output is correct
14 Correct 151 ms 24288 KB Output is correct
15 Correct 121 ms 25572 KB Output is correct
16 Correct 125 ms 23768 KB Output is correct
17 Correct 121 ms 25932 KB Output is correct
18 Correct 103 ms 24056 KB Output is correct
19 Correct 138 ms 27432 KB Output is correct
20 Correct 59 ms 18156 KB Output is correct
21 Correct 70 ms 18240 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5024 KB Output is correct
3 Correct 5 ms 5204 KB Output is correct
4 Correct 5 ms 5156 KB Output is correct
5 Correct 4 ms 5204 KB Output is correct
6 Correct 6 ms 5160 KB Output is correct
7 Correct 5 ms 5204 KB Output is correct
8 Correct 4 ms 5204 KB Output is correct
9 Correct 4 ms 5112 KB Output is correct
10 Correct 8 ms 5116 KB Output is correct
11 Correct 49 ms 13608 KB Output is correct
12 Correct 60 ms 16060 KB Output is correct
13 Correct 112 ms 19772 KB Output is correct
14 Correct 151 ms 24288 KB Output is correct
15 Correct 121 ms 25572 KB Output is correct
16 Correct 125 ms 23768 KB Output is correct
17 Correct 121 ms 25932 KB Output is correct
18 Correct 103 ms 24056 KB Output is correct
19 Correct 138 ms 27432 KB Output is correct
20 Correct 59 ms 18156 KB Output is correct
21 Correct 70 ms 18240 KB Output is correct
22 Correct 278 ms 30236 KB Output is correct
23 Correct 250 ms 28120 KB Output is correct
24 Correct 203 ms 27976 KB Output is correct
25 Correct 295 ms 33784 KB Output is correct
26 Correct 230 ms 29700 KB Output is correct
27 Correct 250 ms 28316 KB Output is correct
28 Correct 42 ms 9800 KB Output is correct
29 Correct 187 ms 20892 KB Output is correct
30 Correct 146 ms 21352 KB Output is correct
31 Correct 164 ms 21408 KB Output is correct
32 Correct 210 ms 25984 KB Output is correct