제출 #702235

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
702235		SamNguyen	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	166 ms	24224 KiB

oneway

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

컴파일 시 표준 에러 (stderr) 메시지

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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40