oj.uz

Submission #1006234

# Submission time Handle Problem Language Result Execution time Memory
1006234 2024-06-23T15:00:36 Z LOLOLO One-Way Streets (CEOI17_oneway) C++17
100 / 100
 122 ms 29268 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (ll)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())

const int N = 1e5 + 1e3;

int n, m;
bool is[N];
int low[N], num[N], timeDfs = 1;
vector <pair <int, int>> g[N];

void dfs(int u, int pre) {
    num[u] = low[u] = ++timeDfs;
    for (auto x : g[u]) {
        if (x.s == pre) 
            continue;

        if (num[x.f] == 0) {
            dfs(x.f, x.s);
            low[u] = min(low[u], low[x.f]);
            if (low[x.f] == num[x.f]) {
                is[x.s] = 1;
            }
        } else low[u] = min(low[u], num[x.f]);
    }
}

char ans[N];
int u[N], v[N];

struct DSU{
    vector <int> p, sz;
    void ass(int n) {
        p.assign(n + 1, 0);
        sz.assign(n + 1, 1);
    }

    int get(int a) {
        return p[a] ? get(p[a]) : a;
    }

    void unite(int a, int b) {
        a = get(a), b = get(b);
        if (a == b)
            return;

        if (sz[a] < sz[b]) 
            swap(a, b);

        sz[a] += sz[b];
        p[b] = a;
    }
};

vector <pair <int, int>> ed[N];
int p[N][20], in[N], ou[N], timer = 1, up[N], down[N], used[N];

void dfs1(int u, int v) {
    p[u][0] = v;
    for (int j = 1; j < 20; j++) 
        p[u][j] = p[p[u][j - 1]][j - 1];

    in[u] = ++timer;
    for (auto x : ed[u]) {
        if (x.f == v)
            continue;

        dfs1(x.f, u);
    }

    ou[u] = timer;
}

int anc(int a, int b) {
    return in[a] <= in[b] && ou[a] >= in[b];
}

int lca(int a, int b) {
    if (anc(a, b))
        return a;

    if (anc(b, a))
        return b;

    for (int j = 19; j >= 0; j--) {
        if (anc(p[a][j], b) == 0)
            a = p[a][j];
    }

    return p[a][0];
}

void dfs2(int t, int id) { 
    used[t] = 1;
    if (down[in[t] - 1] != down[ou[t]]) {
        if (v[id] == t) {
            ans[id] = 'R';
        } else {
            ans[id] = 'L';
        }
    }

    if (up[in[t] - 1] != up[ou[t]]) {
        if (u[id] == t) {
            ans[id] = 'R';
        } else {
            ans[id] = 'L';
        }
    }

    for (auto x : ed[t]) {
        if (x.s == id)
            continue;

        dfs2(x.f, x.s);
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> u[i] >> v[i];
        g[u[i]].push_back({v[i], i});
        g[v[i]].push_back({u[i], i});
    }

    for (int i = 1; i <= n; i++)
        if (!num[i]) 
            dfs(i, 0);

    DSU D;
    D.ass(n + 1);

    for (int i = 1; i <= m; i++) {
        ans[i] = 'B';
        if (is[i] == 0) { 
            D.unite(u[i], v[i]); 
        }
    }

    for (int i = 1; i <= m; i++) {
        if (is[i]) {
            u[i] = D.get(u[i]), v[i] = D.get(v[i]);
            ed[u[i]].pb({v[i], i});
            ed[v[i]].pb({u[i], i});
        }
    }

    for (int i = 1; i <= n; i++) {
        int t = D.get(i);
        if (sz(ed[t]) && in[t] == 0)
            dfs1(t, t);
    }

    int p;
    cin >> p;

    for (int i = 0; i < p; i++) {
        int a, b;
        cin >> a >> b;
        a = D.get(a), b = D.get(b);
        if (a == b)
            continue;

        int c = lca(a, b);
        up[in[a]]++, up[in[c]]--;
        down[in[b]]++, down[in[c]]--;
    }

    for (int i = 1; i < N; i++) {
        up[i] += up[i - 1];
        down[i] += down[i - 1];
    }

    for (int i = 1; i <= n; i++) {
        int t = D.get(i);
        if (used[t] == 0)
            dfs2(t, 0);
    }

    for (int i = 1; i <= m; i++) {
        cout << ans[i];
    }

    cout << '\n';
}

/*
5 6
1 2
1 2
4 3
2 3
1 3
5 1
2
4 5
1 3
*/

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8284 KB Output is correct
2 Correct 2 ms 8284 KB Output is correct
3 Correct 2 ms 8476 KB Output is correct
4 Correct 2 ms 8536 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8280 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 2 ms 8284 KB Output is correct
10 Correct 2 ms 8284 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8284 KB Output is correct
2 Correct 2 ms 8284 KB Output is correct
3 Correct 2 ms 8476 KB Output is correct
4 Correct 2 ms 8536 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8280 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 2 ms 8284 KB Output is correct
10 Correct 2 ms 8284 KB Output is correct
11 Correct 47 ms 14676 KB Output is correct
12 Correct 45 ms 18096 KB Output is correct
13 Correct 53 ms 19792 KB Output is correct
14 Correct 50 ms 23376 KB Output is correct
15 Correct 55 ms 23884 KB Output is correct
16 Correct 63 ms 25168 KB Output is correct
17 Correct 67 ms 26452 KB Output is correct
18 Correct 61 ms 25092 KB Output is correct
19 Correct 65 ms 27436 KB Output is correct
20 Correct 45 ms 17488 KB Output is correct
21 Correct 40 ms 18004 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8284 KB Output is correct
2 Correct 2 ms 8284 KB Output is correct
3 Correct 2 ms 8476 KB Output is correct
4 Correct 2 ms 8536 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 2 ms 8280 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 2 ms 8284 KB Output is correct
10 Correct 2 ms 8284 KB Output is correct
11 Correct 47 ms 14676 KB Output is correct
12 Correct 45 ms 18096 KB Output is correct
13 Correct 53 ms 19792 KB Output is correct
14 Correct 50 ms 23376 KB Output is correct
15 Correct 55 ms 23884 KB Output is correct
16 Correct 63 ms 25168 KB Output is correct
17 Correct 67 ms 26452 KB Output is correct
18 Correct 61 ms 25092 KB Output is correct
19 Correct 65 ms 27436 KB Output is correct
20 Correct 45 ms 17488 KB Output is correct
21 Correct 40 ms 18004 KB Output is correct
22 Correct 122 ms 26452 KB Output is correct
23 Correct 106 ms 24916 KB Output is correct
24 Correct 105 ms 25084 KB Output is correct
25 Correct 108 ms 29268 KB Output is correct
26 Correct 121 ms 25940 KB Output is correct
27 Correct 107 ms 25008 KB Output is correct
28 Correct 45 ms 10408 KB Output is correct
29 Correct 82 ms 16980 KB Output is correct
30 Correct 77 ms 17748 KB Output is correct
31 Correct 74 ms 15364 KB Output is correct
32 Correct 91 ms 23384 KB Output is correct