oj.uz

Submission #580077

# Submission time Handle Problem Language Result Execution time Memory
580077 2022-06-20T14:29:13 Z thezomb1e One-Way Streets (CEOI17_oneway) C++17
60 / 100
 3000 ms 20708 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

struct DSU {
    vector<int> e;
    DSU(int n) { e.assign(n + 5, -1); }
    int get(int x) { return (e[x] <= -1 ? x : e[x] = get(e[x])); }
    bool unite(int x, int y) {
        x = get(x), y = get(y);
        if (x == y) return false;
        if (-e[x] < -e[y]) swap(x, y);
        e[x] += e[y]; e[y] = x;
        return true;
    }
};

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});
            }
        }
        vector<int> path;
        vector<bool> vis(n + 5, false);
        function<bool(int, int)> dfs = [&](int f, int ed) -> bool {
            vis[f] = true;
            if (f == ed) return true;
            for (pi to : e_comp[f]) {
                if (!vis[to.ft]) {
                    if (dfs(to.ft, ed)) {
                        path.pb(to.sd);
                        return true;
                    }
                }
            }
            return false;
        };
        for (pi x : need) {
            while (!path.empty()) path.pop_back();
            fill(all(vis), false);
            dfs(comp[x.ft], comp[x.sd]);
            for (int x : path) {
                if (x > 0) 
                    ans[x] = 'R';
                else 
                    ans[-x] = 'L';
            }
        }
    }
    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 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 5 ms 492 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 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 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 5 ms 492 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 45 ms 7368 KB Output is correct
12 Correct 66 ms 9108 KB Output is correct
13 Correct 49 ms 11212 KB Output is correct
14 Correct 74 ms 13236 KB Output is correct
15 Correct 99 ms 14080 KB Output is correct
16 Correct 84 ms 14880 KB Output is correct
17 Correct 307 ms 18416 KB Output is correct
18 Correct 224 ms 14884 KB Output is correct
19 Correct 413 ms 18732 KB Output is correct
20 Correct 52 ms 9584 KB Output is correct
21 Correct 45 ms 9244 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 5 ms 492 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 45 ms 7368 KB Output is correct
12 Correct 66 ms 9108 KB Output is correct
13 Correct 49 ms 11212 KB Output is correct
14 Correct 74 ms 13236 KB Output is correct
15 Correct 99 ms 14080 KB Output is correct
16 Correct 84 ms 14880 KB Output is correct
17 Correct 307 ms 18416 KB Output is correct
18 Correct 224 ms 14884 KB Output is correct
19 Correct 413 ms 18732 KB Output is correct
20 Correct 52 ms 9584 KB Output is correct
21 Correct 45 ms 9244 KB Output is correct
22 Execution timed out 3049 ms 20708 KB Time limit exceeded
23 Halted 0 ms 0 KB -