Submission #702213

#TimeUsernameProblemLanguageResultExecution timeMemory
702213SamNguyenOne-Way Streets (CEOI17_oneway)C++14
0 / 100
4 ms3572 KiB
#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 (stderr)

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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...