oj.uz

답안 #1005182

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1005182 2024-06-22T08:31:26 Z Essa2006 One-Way Streets (CEOI17_oneway) C++14
0 / 100
 0 ms 344 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;
int n, m, p, time_;
vector<int> Vis, up, dpth, upx, upy, dis, fin, U, V;
vector<vector<int>> A, X, Y;
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);
}


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++) {
        if (dis[X[u][i]] < dis[u] || fin[X[u][i]] > fin[u]) {
            if (dis[X[u][i]] < dis[u] && fin[u] <fin[X[u][i]]) {
                upx[u] = min(upx[u], dpth[X[u][i]]);
            }
            else {
                upx[u] = -1;
            }
        }

    }
    for (int i = 0; i < Y[u].size(); i++) {
        if (dis[Y[u][i]] < dis[u] || fin[Y[u][i]] > fin[u]) {
            if (dis[Y[u][i]] < dis[u] && fin[u] <fin[Y[u][i]]) {
                upy[u] = min(upy[u], dpth[Y[u][i]]);
            }
            else {
                upy[u] = -1;
            }
        }
    }

    if (up[u] == dpth[u]) {
        if (upy[u] < dpth[u] && !(upx[u] < dpth[u])) {
            if (dir[{u, p}]) {
                go[{u, p}] = 1;
            }
            else {
                go[{p, u}] = 1;
            }
        }
        else if (upx[u] < dpth[u] && !(upy[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 'void dfs(int, int)':
oneway.cpp:37:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for (int i = 0; i < X[u].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
oneway.cpp:48:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for (int i = 0; i < Y[u].size(); i++) {
      |                     ~~^~~~~~~~~~~~~

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -