답안 #1005209

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1005209 2024-06-22T08:53:33 Z Essa2006 One-Way Streets (CEOI17_oneway) C++14
0 / 100
3000 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);
    }
    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 (dpth[Lca[v][i]] != dpth[Lca[u][i]]) {
            u = Lca[u][i], v = Lca[v][i];
        }
    }
}

void dfs(int u, int p = -1) {
    Vis[u] = 1;
    up[u] = dpth[u];
    if (p != -1) {
        Lca[u][0] = p;
    }
    for (int i = 1; i <= lg; i++) {
        Lca[u][i] = Lca[Lca[u][i - 1]][i - 1];
    }
    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++) {
        if (fin[X[u][i]] < dis[u] || dis[X[u][i]] > fin[u]) {
            upx[u] = dpth[lca(u, X[u][i])];
        }
        upx[u] = min(upx[u], dpth[X[u][i]]);
    }
    for (int i = 0; i < Y[u].size(); i++) {
        if (fin[Y[u][i]] < dis[u] || dis[Y[u][i]] > fin[u]) {
            upy[u] = dpth[lca(u, Y[u][i])];
        }
        upy[u] = min(upy[u], dpth[Y[u][i]]);
    }

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

void calc(int u) {
    dis[u] = ++time_;
    for (auto v : A[u]) {
        if (!dis[v]) {
            calc(v);
        }
    }
    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);
    }

    calc(1);
    dpth[1] = 0;
    dfs(1);

    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 'int lca(int, int)':
oneway.cpp:36:1: warning: no return statement in function returning non-void [-Wreturn-type]
   36 | }
      | ^
oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (int i = 0; i < X[u].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
oneway.cpp:65:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for (int i = 0; i < Y[u].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3056 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3056 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3056 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -