oj.uz

답안 #702232

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
702232 2023-02-23T10:52:27 Z SamNguyen One-Way Streets (CEOI17_oneway) C++14
0 / 100
 2 ms 3028 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<int> agg;
    vector<pair<int, bool>> reqs;

    void dfs(int u = 0, int p = -1) {
        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:
    Tree() {}
    Tree(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) {
        dfs();

        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++;
    }
}

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);
    }
}

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

Subtask #1
0 / 30.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 40.0

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