oj.uz

Submission #702235

# Submission time Handle Problem Language Result Execution time Memory
702235 2023-02-23T10:58:21 Z SamNguyen One-Way Streets (CEOI17_oneway) C++14
100 / 100
 166 ms 24224 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 Forest {
private:
    int n;
    vector<vector<tuple<int, int, bool>>> adj;
    vector<int> agg;
    vector<pair<int, bool>> reqs;
    vector<bool> is_visited;

    void dfs(int u = 0, int p = -1) {
        if (is_visited[u])
            return;
        is_visited[u] = true;

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

            dfs(v, u);
            agg[u] += agg[v];

            if (agg[v] != 0)
                reqs.emplace_back(i, (agg[v] > 0 ? not dir : dir));
        }
    }

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

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

    inline void set_dir(int x, int y) {
        agg[x]++, agg[y]--;
    }

    template <class Func>
    inline void FOR_REQS(Func f) {
        is_visited.assign(n, false);
        for (int u = 0; u < n; u++) if (not is_visited[u])
            dfs(u);

        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 pi = -1) {
    tin[u] = low[u] = ++COUNTER;
    st.push(u);
    on_stack[u] = true;

    for (int i : adj[u]) if (i != pi) {
        int v = OTHER_NODE(i, u);
        if (tin[v] == 0) {
            dfs(v, i);
            minimise(low[u], low[v]);
        }
        else
            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++;
    }
}

Forest forest;

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

    forest = Forest(COUNT_BCCS);

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

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

    string ans(M, 'B');

    forest.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:170:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |         freopen(INPFILE, "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
oneway.cpp:171:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  171 |         freopen(OUTFILE, "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.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 2 ms 3048 KB Output is correct
4 Correct 3 ms 3156 KB Output is correct
5 Correct 4 ms 3156 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 2 ms 3156 KB Output is correct
8 Correct 3 ms 3156 KB Output is correct
9 Correct 2 ms 3084 KB Output is correct
10 Correct 3 ms 3044 KB Output is correct

Subtask #2
30.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 2 ms 3048 KB Output is correct
4 Correct 3 ms 3156 KB Output is correct
5 Correct 4 ms 3156 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 2 ms 3156 KB Output is correct
8 Correct 3 ms 3156 KB Output is correct
9 Correct 2 ms 3084 KB Output is correct
10 Correct 3 ms 3044 KB Output is correct
11 Correct 67 ms 7288 KB Output is correct
12 Correct 80 ms 8464 KB Output is correct
13 Correct 80 ms 9560 KB Output is correct
14 Correct 88 ms 11648 KB Output is correct
15 Correct 93 ms 12620 KB Output is correct
16 Correct 107 ms 15756 KB Output is correct
17 Correct 93 ms 17920 KB Output is correct
18 Correct 145 ms 15680 KB Output is correct
19 Correct 91 ms 19008 KB Output is correct
20 Correct 74 ms 8244 KB Output is correct
21 Correct 72 ms 7864 KB Output is correct

Subtask #3
40.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 2 ms 3048 KB Output is correct
4 Correct 3 ms 3156 KB Output is correct
5 Correct 4 ms 3156 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 2 ms 3156 KB Output is correct
8 Correct 3 ms 3156 KB Output is correct
9 Correct 2 ms 3084 KB Output is correct
10 Correct 3 ms 3044 KB Output is correct
11 Correct 67 ms 7288 KB Output is correct
12 Correct 80 ms 8464 KB Output is correct
13 Correct 80 ms 9560 KB Output is correct
14 Correct 88 ms 11648 KB Output is correct
15 Correct 93 ms 12620 KB Output is correct
16 Correct 107 ms 15756 KB Output is correct
17 Correct 93 ms 17920 KB Output is correct
18 Correct 145 ms 15680 KB Output is correct
19 Correct 91 ms 19008 KB Output is correct
20 Correct 74 ms 8244 KB Output is correct
21 Correct 72 ms 7864 KB Output is correct
22 Correct 158 ms 21300 KB Output is correct
23 Correct 149 ms 19820 KB Output is correct
24 Correct 166 ms 20000 KB Output is correct
25 Correct 149 ms 24224 KB Output is correct
26 Correct 142 ms 21016 KB Output is correct
27 Correct 149 ms 19900 KB Output is correct
28 Correct 88 ms 7128 KB Output is correct
29 Correct 123 ms 10620 KB Output is correct
30 Correct 121 ms 10668 KB Output is correct
31 Correct 120 ms 11120 KB Output is correct
32 Correct 135 ms 15260 KB Output is correct