oj.uz

Submission #702213

# Submission time Handle Problem Language Result Execution time Memory
702213 2023-02-23T10:24:27 Z SamNguyen One-Way Streets (CEOI17_oneway) C++14
0 / 100
 4 ms 3572 KB 
#include <bits/stdc++.h>
using namespace std;

#define INPFILE "CEOI17_oneway.inp"
#define OUTFILE "CEOI17_oneway.out"

template <class T1, class T2>
inline bool minimise(T1 &x, T2 y) {
    if (x > y) { x = y; return true; }
    return false;
}

template <class T1, class T2>
inline bool maximise(T1 &x, T2 y) {
    if (x < y) { x = y; return true; }
    return false;
}

class Tree {
private:
    int n;
    vector<vector<tuple<int, int, bool>>> adj;
    vector<pair<int, int>> par;
    vector<pair<int, bool>> reqs;

//    void dfs(int u = 0, int p = -1) {
//        for (const auto &e : adj[u]) {
//            int v = e.first;
//            if (v == p) {
//                par[v] = e;
//                continue;
//            }
//            dfs(v, u);
//        }
//    }
//
//

    bool dfs_dir(int u, int y, int p = -1) {
//        cerr << "dfs_dir " << u << " " << y << endl;

        if (u == y)
            return true;

        for (const auto &e : adj[u]) {
            int v, i; bool dir;
            tie(v, i, dir) = e;
            if (v == p)
                continue;

            if (dfs_dir(v, y, u)) {
                reqs.emplace_back(i, dir);
                return true;
            }
        }

        return false;
    }

public:
    Tree() {}
    Tree(int n): n(n) {
        adj.assign(n, vector<tuple<int, int, bool>>());
    }

    inline void add_edge(int u, int v, int i) {
        adj[u].emplace_back(v, i, true);
        adj[v].emplace_back(u, i, false);
    }

    void traverse() {
//        par.assign(n, make_pair(-1, -1));
//        dfs();
    }

    inline void set_dir(int x, int y) {
        dfs_dir(x, y);
    }

    template <class Func>
    inline void FOR_REQS(Func f) {
        for (const auto &e : reqs)
            f(e.first, e.second);
    }
};

const int MAX = 1e5 + 7;
int N, M, P;
vector<pair<int, int>> edges;
vector<int> adj[MAX];
vector<pair<int, int>> dirs;

inline int OTHER_NODE(int i, int u) {
    return edges[i].first ^ edges[i].second ^ u;
}

void input() {
    cin >> N >> M;
    for (int t = M; t--; ) {
        int u, v; cin >> u >> v;
        adj[u].push_back(edges.size());
        adj[v].push_back(edges.size());
        edges.emplace_back(u, v);
    }

    cin >> P;
    for (int t = P; t--; ) {
        int x, y; cin >> x >> y;
        dirs.emplace_back(x, y);
    }
}

int COUNTER, tin[MAX], low[MAX], root[MAX], comp[MAX];
int COUNT_BCCS;
stack<int> st;
bool on_stack[MAX];

void dfs(int u, int p = 0) {
    tin[u] = low[u] = ++COUNTER;
    st.push(u);
    on_stack[u] = true;

    for (int i : adj[u]) {
        int v = OTHER_NODE(i, u);
        if (tin[v] == 0) {
            dfs(v, u);
            minimise(low[u], low[v]);
        }
        else if (v != p)
            minimise(low[u], tin[v]);
    }

    if (low[u] == tin[u]) {
        while (true) {
            int v = st.top(); st.pop();
            on_stack[v] = false;
            root[v] = u;
            comp[v] = COUNT_BCCS;
            if (v == u)
                break;
        }

        COUNT_BCCS++;
    }
}

Tree tree;

void init() {
    COUNTER = COUNT_BCCS = 0;
    memset(tin, 0, sizeof tin);
    for (int u = 1; u <= N; u++) if (tin[u] == 0)
        dfs(u);

    tree = Tree(COUNT_BCCS);

    for (int i = 0; i < M; i++) {
        int u, v;
        tie(u, v) = edges[i];
        if (comp[u] == comp[v])
            continue;
        tree.add_edge(comp[u], comp[v], i);
    }

    tree.traverse();
}

void solve() {
    for (const auto &p : dirs) {
        int x, y;
        tie(x, y) = p;
        tree.set_dir(comp[x], comp[y]);
    }

    string ans(M, 'B');

    tree.FOR_REQS([&](int i, bool dir) {
        ans[i] = (dir ? 'R' : 'L');
    });

    cout << ans;
}

int main(void) {
    if (fopen(INPFILE, "r")) {
        freopen(INPFILE, "r", stdin);
        freopen(OUTFILE, "w", stdout);
    }

    input();
    init();
    solve();

    return 0;
}

Compilation message

oneway.cpp: In function 'int main()':
oneway.cpp:186:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  186 |         freopen(INPFILE, "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
oneway.cpp:187:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  187 |         freopen(OUTFILE, "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 3 ms 3028 KB Output is correct
4 Correct 2 ms 3088 KB Output is correct
5 Correct 4 ms 3544 KB Output is correct
6 Correct 2 ms 3156 KB Output is correct
7 Correct 3 ms 3572 KB Output is correct
8 Correct 3 ms 3156 KB Output is correct
9 Incorrect 2 ms 3028 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 3 ms 3028 KB Output is correct
4 Correct 2 ms 3088 KB Output is correct
5 Correct 4 ms 3544 KB Output is correct
6 Correct 2 ms 3156 KB Output is correct
7 Correct 3 ms 3572 KB Output is correct
8 Correct 3 ms 3156 KB Output is correct
9 Incorrect 2 ms 3028 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 3 ms 3028 KB Output is correct
4 Correct 2 ms 3088 KB Output is correct
5 Correct 4 ms 3544 KB Output is correct
6 Correct 2 ms 3156 KB Output is correct
7 Correct 3 ms 3572 KB Output is correct
8 Correct 3 ms 3156 KB Output is correct
9 Incorrect 2 ms 3028 KB Output isn't correct
10 Halted 0 ms 0 KB -