oj.uz

Submission #580142

# Submission time Handle Problem Language Result Execution time Memory
580142 2022-06-20T16:05:35 Z thezomb1e One-Way Streets (CEOI17_oneway) C++17
100 / 100
 318 ms 35400 KB 
//thatsramen

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define eb emplace_back
#define pb push_back
#define ft first
#define sd second
#define pi pair<int, int>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define dbg(...) dbg_out(__VA_ARGS__)

using ll = long long;
using ld = long double;
using namespace std;
using namespace __gnu_pbds;

//Constants
const ll INF = 5 * 1e18;
const int IINF = 2 * 1e9;
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ld PI = 3.14159265359;

//Templates
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) {return os << '(' << p.first << ", " << p.second << ')';}
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) {os << '['; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << ']';}
void dbg_out() {cerr << endl;}
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << H << ' '; dbg_out(T...); }
template<typename T> void mins(T& x, T y) {x = min(x, y);}
template<typename T> void maxs(T& x, T y) {x = max(x, y);}
template<typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using omset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

//order_of_key(k): number of elements strictly less than k
//find_by_order(k): k-th element in the set

void setPrec() {cout << fixed << setprecision(15);}
void unsyncIO() {cin.tie(0)->sync_with_stdio(0);}
void setIn(string s) {freopen(s.c_str(), "r", stdin);}
void setOut(string s) {freopen(s.c_str(), "w", stdout);}
void setIO(string s = "") {
    unsyncIO(); setPrec();
    if(s.size()) setIn(s + ".in"), setOut(s + ".out");
}

// #define TEST_CASES

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<pi>> e(n + 5);
    vector<pi> edges;
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        e[u].pb({v, i});
        e[v].pb({u, i});
        edges.pb({u, v});
    }
    int q; cin >> q;
    vector<pi> need(q);
    for (int i = 0; i < q; i++) {
        cin >> need[i].ft >> need[i].sd;
    }
    vector<bool> isBridge(m + 5, false);
    vector<char> ans(m + 5, 'B');
    vector<int> comp(n + 5);

    {
        vector<bool> vis(n + 5, false);
        vector<int> dp(n + 5, IINF), dep(n + 5, 0);
        function<void(int, int)> find_bridges = [&](int f, int p) {
            vis[f] = true;
            dp[f] = dep[f];
            for (pi to : e[f]) {
                if (to.ft == p) continue;
                if (!vis[to.ft]) {
                    dep[to.ft] = dep[f] + 1;
                    find_bridges(to.ft, f);
                    if (dp[to.ft] > dep[f]) {
                        // bridge found, yay!
                        isBridge[to.sd] = true;
                    }
                    mins(dp[f], dp[to.ft]);
                } else mins(dp[f], dep[to.ft]);
            }
        };
        function<void(int, int)> color_component = [&](int f, int cc) {
            vis[f] = true; comp[f] = cc;
            for (pi to : e[f]) {
                if (!vis[to.ft]) 
                    if (!isBridge[to.sd])
                        color_component(to.ft, cc);
            }
        };
        for (int i = 1; i <= n; i++) {
            if (!vis[i]) 
                find_bridges(i, -1);
        }
        fill(all(vis), false);
        for (int i = 1, pp = 1; i <= n; i++) {
            if (!vis[i])
                color_component(i, pp++);
        }
    }


    {
        vector<vector<pi>> e_comp(n + 5);
        for (int i = 1; i <= m; i++) {
            if (isBridge[i]) {
                int u = comp[edges[i - 1].ft], v = comp[edges[i - 1].sd];
                e_comp[u].pb({v, i}); e_comp[v].pb({u, -i});
            }
        }
        int LOG = 17;
        vector<vector<int>> jump(n + 5, vector<int> (LOG + 5, -1));
        vector<int> dir_up(n + 5, 0), dir_down(n + 5, 0), dep(n + 5, 0); 
        function<void(int, int)> dfs1 = [&](int f, int p) {
            jump[f][0] = p;
            for (int i = 1; i <= LOG; i++) 
                jump[f][i] = jump[jump[f][i - 1]][i - 1];
            
            for (pi to : e_comp[f]) {
                if (to.ft != p && to.ft != f) {
                    dep[to.ft] = dep[f] + 1;
                    dfs1(to.ft, f);
                }
            }
        };
        for (int i = 1; i <= n; i++) {
            if (jump[i][0] == -1) 
                dfs1(i, i);
        }
        auto get = [&](int u, int v) -> int {
            if (dep[u] < dep[v]) swap(u, v);
            for (int i = LOG; i >= 0; i--) {
                int to = jump[u][i];
                if (dep[to] >= dep[v]) u = to;
            }
            if (u == v) return u;
            for (int i = LOG; i >= 0; i--) {
                int uu = jump[u][i], vv = jump[v][i];
                if (uu != vv) {
                    u = uu; v = vv;
                }
            }
            return jump[u][0];
        };
        for (pi x : need) {
            int u = comp[x.ft], v = comp[x.sd];
            int lca = get(u, v);
            dir_up[lca]--; dir_down[lca]--;
            dir_up[u]++; dir_down[v]++;
        }
        vector<bool> vis(n + 5, false);
        vector<int> dp(n + 5, 0);
        function<void(int)> dfs2 = [&](int f) {
            vis[f] = true;
            for (pi to : e_comp[f]) {
                if (!vis[to.ft]) {
                    dfs2(to.ft);
                    dir_up[f] += dir_up[to.ft];
                    dir_down[f] += dir_down[to.ft];
                    if (dir_up[to.ft] > 0) {
                        if (to.sd < 0) {
                            ans[(to.sd > 0 ? 1 : -1) * to.sd] = 'R';
                        } else {
                            ans[(to.sd > 0 ? 1 : -1) * to.sd] = 'L';
                        }
                    }
                    if (dir_down[to.ft] > 0) {
                        if (to.sd < 0) {
                            ans[(to.sd > 0 ? 1 : -1) * to.sd] = 'L';
                        } else {
                            ans[(to.sd > 0 ? 1 : -1) * to.sd] = 'R';
                        }
                    }
                }
            }
        };
        for (int i = 1; i <= n; i++) { 
            if (!vis[i])
                dfs2(i);
        }
    }
    for (int i = 1; i <= m; i++) {
        cout << ans[i];
    }
}

int main() {
    setIO();

    int tt = 1;
    #ifdef TEST_CASES
        cin >> tt;
    #endif

    while (tt--)
        solve();

    return 0;
}

Compilation message

oneway.cpp: In function 'void setIn(std::string)':
oneway.cpp:44:30: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 | void setIn(string s) {freopen(s.c_str(), "r", stdin);}
      |                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'void setOut(std::string)':
oneway.cpp:45:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 | void setOut(string s) {freopen(s.c_str(), "w", stdout);}
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 42 ms 9024 KB Output is correct
12 Correct 67 ms 12160 KB Output is correct
13 Correct 62 ms 16772 KB Output is correct
14 Correct 107 ms 23276 KB Output is correct
15 Correct 108 ms 25264 KB Output is correct
16 Correct 143 ms 27588 KB Output is correct
17 Correct 151 ms 29296 KB Output is correct
18 Correct 170 ms 27616 KB Output is correct
19 Correct 150 ms 30640 KB Output is correct
20 Correct 67 ms 15192 KB Output is correct
21 Correct 62 ms 14900 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 42 ms 9024 KB Output is correct
12 Correct 67 ms 12160 KB Output is correct
13 Correct 62 ms 16772 KB Output is correct
14 Correct 107 ms 23276 KB Output is correct
15 Correct 108 ms 25264 KB Output is correct
16 Correct 143 ms 27588 KB Output is correct
17 Correct 151 ms 29296 KB Output is correct
18 Correct 170 ms 27616 KB Output is correct
19 Correct 150 ms 30640 KB Output is correct
20 Correct 67 ms 15192 KB Output is correct
21 Correct 62 ms 14900 KB Output is correct
22 Correct 318 ms 30064 KB Output is correct
23 Correct 244 ms 29968 KB Output is correct
24 Correct 214 ms 30392 KB Output is correct
25 Correct 289 ms 35400 KB Output is correct
26 Correct 243 ms 31292 KB Output is correct
27 Correct 204 ms 30116 KB Output is correct
28 Correct 43 ms 5272 KB Output is correct
29 Correct 80 ms 17236 KB Output is correct
30 Correct 88 ms 17396 KB Output is correct
31 Correct 76 ms 17832 KB Output is correct
32 Correct 120 ms 23620 KB Output is correct