oj.uz

Submission #1005298

# Submission time Handle Problem Language Result Execution time Memory
1005298 2024-06-22T09:59:28 Z Essa2006 One-Way Streets (CEOI17_oneway) C++14
0 / 100
 1 ms 348 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)

const int inf = 1e9, lg = 20;
int n, m, p, time_;
vector<int> Vis, up, dpth, upx, upy, dis, fin, U, V;
vector<vector<int>> A, X, Y, Lca;
map<array<int, 2>, int> dir, has, go;

void pre() {
    Vis.resize(n + 1), up.resize(n + 1, inf), dpth.resize(n + 1, inf), upx.resize(n + 1, inf), upy.resize(n + 1, inf), dis.resize(n + 1), fin.resize(n + 1), U.resize(m), V.resize(m);
    A.resize(n + 1), X.resize(n + 1), Y.resize(n + 1), Lca.resize(n + 1, vector<int>(lg + 1));
}

int lca(int u, int v) {
    if (dpth[u] > dpth[v]) {
        swap(u, v);
    }

    // u

    // v

    for (int i = lg; i >= 0; i--) {
        if (dpth[Lca[v][i]] >= dpth[u]) {
            v = Lca[v][i];
        }
    }

    for (int i = lg; i >= 0; i--) {
        if (Lca[v][i] != Lca[u][i]) {
            u = Lca[u][i], v = Lca[v][i];
        }
    }
    if (u != v) {
        u = Lca[u][0];
    }
    return u;
}

void dfs(int u, int p = -1) {
    Vis[u] = 1;
    up[u] = dpth[u];
    for (auto v : A[u]) {
        if (v == p) {
            continue;
        }
        if (!Vis[v]) {
            dpth[v] = dpth[u] + 1;
            dfs(v, u);
            upx[u] = min(upx[u], upx[v]);
            upy[u] = min(upy[u], upy[v]);
        }
        up[u] = min(up[u], up[v]);
    }

    for (int i = 0; i < X[u].size(); i++) {
        upx[u] = min(upx[u], dpth[lca(u, X[u][i])]);
    }
    for (int i = 0; i < Y[u].size(); i++) {
        upy[u] = min(upy[u], dpth[lca(u, Y[u][i])]);
    }

    if (up[u] == dpth[u] && has[{u, p}] == 1) {
        assert(max(upx[u], upy[u]) >= dpth[u]);
        if (upy[u] < dpth[u]) {
            go[{u, p}] = 1;
        }
        else {
            go[{p, u}] = 1;
        }
    }
}

void calc(int u, int p = -1) {
    dis[u] = ++time_;
    Lca[u][0] = (p == -1 ? u : p);
    for (int i = 1; i <= lg; i++) {
        Lca[u][i] = Lca[Lca[u][i - 1]][i - 1];
    }
    for (auto v : A[u]) {
        if (!dis[v]) {
            dpth[v] = dpth[u] + 1;
            calc(v, u);
        }
    }
    fin[u] = ++time_;
}

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

    cin >> n >> m;
    pre();

    for (int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;

        A[u].push_back(v);
        A[v].push_back(u);
        dir[{u, v}] = 1;
        has[{u, v}]++;
        has[{v, u}]++;

        U[i] = u, V[i] = v;
    }

    cin >> p;
    for (int i = 0 ; i < p; i++) {
        int x, y;
        cin >> x >> y;

        X[y].push_back(x);
        Y[x].push_back(y);
    }

    for (int i = 1; i <= n; i++) {
        if (Vis[i]) {
            continue;
        }
        dpth[i] = 0;
        calc(i);
        dfs(i);
    }

    for (int i = 0; i < m; i++) {
        int u = U[i], v = V[i];
        if (!(go[{u, v}] || go[{v, u}]) || u == v || has[{u, v}] != 1) {
            cout << 'B';
            continue;
        }
        if (go[{u, v}]) {
            cout << 'R';
            continue;
        }
        cout << 'L';
    }
}

Compilation message

oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:63:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for (int i = 0; i < X[u].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
oneway.cpp:66:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for (int i = 0; i < Y[u].size(); i++) {
      |                     ~~^~~~~~~~~~~~~

Subtask #1
0 / 30.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 40.0

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