oj.uz

Submission #715728

# Submission time Handle Problem Language Result Execution time Memory
715728 2023-03-27T16:54:43 Z Valera_Grinenko One-Way Streets (CEOI17_oneway) C++17
100 / 100
 162 ms 29536 KB 
//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")

#ifdef __APPLE__

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <immintrin.h>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>

#else
#include <bits/stdc++.h>
#endif

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

template<typename T>
bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#if __APPLE__
#define D for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl

template<class ...Ts>
auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }

#else
#define D while (false)
#define LOG(...)
#endif

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct bridges_two_edge_connected_components {
    static const int max_n = -1;
    int m = 0;
    vector<vector<pair<int, int> > > g;
    vector<bool> visited, is_bridge;
    vector<int> tin, low;
    int timer;
    void init(int n) {
        clear(n);
        g.assign(n, {});
    }
    void clear(int n) {
        m = 0;
        g.clear();
        visited.clear(); is_bridge.clear();
        tin.clear(); low.clear();
        timer = 0;
    }
    void add_edge(int a, int b) {
        g[a].pb({b, m});
        g[b].pb({a, m});
        m++;
    }
    void dfs_bridges(int v, int p = -1) {
        visited[v] = true;
        tin[v] = low[v] = timer++;
        for (auto& to : g[v]) {
            if (to.se == p) continue;
            if (visited[to.fi]) {
                low[v] = min(low[v], tin[to.fi]);
            } else {
                dfs_bridges(to.fi, to.se);
                low[v] = min(low[v], low[to.fi]);
                if (low[to.fi] > tin[v]) is_bridge[to.se] = true;
            }
        }
    }
    vector<bool> find_bridges(int n) {
        is_bridge.assign(m, false);
        timer = 0;
        visited.assign(n, false);
        tin.assign(n, -1);
        low.assign(n, -1);
        for (int i = 0; i < n; ++i) {
            if (!visited[i])
                dfs_bridges(i);
        }
        return is_bridge;
    }
    vector<int> two_edge_component;
    int comp_num;
    void dfs_components(int v) {
        two_edge_component[v] = comp_num;
        for(auto& to : g[v])
            if(two_edge_component[to.fi] == -1 && !is_bridge[to.se])
                dfs_components(to.fi);
    }
    vector<int> find_two_edge_component_nums(int n) {
        find_bridges(n);
        two_edge_component.assign(n, -1);
        comp_num = 0;
        for(int i = 0; i < n; i++)
            if(two_edge_component[i] == -1) {
                dfs_components(i);
                comp_num++;
            }
        return two_edge_component;
    }
    vector<vector<int> > find_two_edge_components(int n) {
        auto component_nums = find_two_edge_component_nums(n);
        int am_components = *max_element(all(component_nums)) + 1;
        vector<vector<int> > components(am_components);
        for(int i = 0; i < n; i++) components[component_nums[i]].pb(i);
        return components;
    }
};

const int max_n = 1e5, K = 18;
vector<pair<int, int> > g[max_n];
int tin[max_n], tout[max_n];
int up[max_n][K];
int timer = 0;
int dep[max_n];
bool used[max_n];

void predfs(int v, int p) {
    used[v] = true;
    tin[v] = ++timer;
    up[v][0] = p;
    for (int i = 1; i < K; i++)
        up[v][i] = up[up[v][i - 1]][i - 1];
    for (auto &x: g[v])
        if (x.fi != p) {
            dep[x.fi] = dep[v] + 1;
            predfs(x.fi, v);
        }
    tout[v] = ++timer;
}

int jump(int x, int d) {
    for (int i = 0; i < K; i++)
        if (((d >> i) & 1)) {
            x = up[x][i];
        }
    return x;
}

bool ancester(int a, int b) {
    return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}

int lca(int a, int b) {
    if (ancester(a, b)) return a;
    if (ancester(b, a)) return b;
    for (int i = K - 1; i >= 0; i--)
        if (!ancester(up[a][i], b))
            a = up[a][i];
    return up[a][0];
}

int kek[max_n][2];

int par_edge[max_n];

void dfs(int v, int p) {
    used[v] = true;
    for(auto& to : g[v])
        if(to.fi != p) {
            par_edge[to.fi] = to.se;
            dfs(to.fi, v);
            kek[v][0] += kek[to.fi][0];
            kek[v][1] += kek[to.fi][1];
        }
}

void solve() {
    int n, m;
    cin >> n >> m;
    bridges_two_edge_connected_components graph;
    graph.init(n);
    vector<pair<int, int> > edges(m);
    for(auto& x : edges) {
        cin >> x.fi >> x.se;
        x.fi--; x.se--;
        graph.add_edge(x.fi, x.se);
    }
    auto component_nums = graph.find_two_edge_component_nums(n);
    for(int i = 0; i < m; i++) {
        int u = component_nums[edges[i].fi];
        int v = component_nums[edges[i].se];
        if(u != v) {
            g[u].pb({v, i});
            g[v].pb({u, i});
        }
    }
    for(int i = 0; i < n; i++) { par_edge[i] = -1; used[i] = false; }
    for(int i = 0; i < n; i++)
        if(!used[i])
            predfs(i, i);
    int p; cin >> p;
    while(p--) {
        int s, t;
        cin >> s >> t;
        s--; t--;
        s = component_nums[s]; t = component_nums[t];
        if(s == t) continue;
        if(ancester(s, t)) {
            kek[t][1]++;
            kek[s][1]--;
        } else if(ancester(t, s)) {
            kek[s][0]++;;
            kek[t][0]--;
        } else {
            int clca = lca(s, t);
            kek[s][0]++;
            kek[clca][0]--;
            kek[t][1]++;
            kek[clca][1]--;
        }
    }
    for(int i = 0; i < n; i++) used[i] = false;
    for(int i = 0; i < n; i++)
        if(!g[i].empty() && !used[i])
            dfs(i, i);
    string ans = string(m, 'B');
    for(int i = 0; i < n; i++)
        if(par_edge[i] != -1) {
            int from = i;
            if(kek[i][0]) ans[par_edge[i]] = (component_nums[edges[par_edge[i]].fi] == from ? 'R' : 'L');
            else if(kek[i][1]) ans[par_edge[i]] = (component_nums[edges[par_edge[i]].fi] == from ? 'L' : 'R');
        }
    cout << ans;
}

signed main() {
//   freopen("input.txt", "r", stdin);
//   freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;

    //cin >> t;

    while (t--) solve();

}

/*
KIVI
*/

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 2 ms 2900 KB Output is correct
5 Correct 2 ms 2900 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 2 ms 2900 KB Output is correct
8 Correct 2 ms 2900 KB Output is correct
9 Correct 2 ms 2772 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 2 ms 2900 KB Output is correct
5 Correct 2 ms 2900 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 2 ms 2900 KB Output is correct
8 Correct 2 ms 2900 KB Output is correct
9 Correct 2 ms 2772 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct
11 Correct 36 ms 9548 KB Output is correct
12 Correct 39 ms 11616 KB Output is correct
13 Correct 55 ms 14900 KB Output is correct
14 Correct 73 ms 19636 KB Output is correct
15 Correct 70 ms 21240 KB Output is correct
16 Correct 102 ms 25656 KB Output is correct
17 Correct 112 ms 26640 KB Output is correct
18 Correct 106 ms 25676 KB Output is correct
19 Correct 98 ms 27608 KB Output is correct
20 Correct 43 ms 14620 KB Output is correct
21 Correct 44 ms 14412 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 2 ms 2900 KB Output is correct
5 Correct 2 ms 2900 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 2 ms 2900 KB Output is correct
8 Correct 2 ms 2900 KB Output is correct
9 Correct 2 ms 2772 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct
11 Correct 36 ms 9548 KB Output is correct
12 Correct 39 ms 11616 KB Output is correct
13 Correct 55 ms 14900 KB Output is correct
14 Correct 73 ms 19636 KB Output is correct
15 Correct 70 ms 21240 KB Output is correct
16 Correct 102 ms 25656 KB Output is correct
17 Correct 112 ms 26640 KB Output is correct
18 Correct 106 ms 25676 KB Output is correct
19 Correct 98 ms 27608 KB Output is correct
20 Correct 43 ms 14620 KB Output is correct
21 Correct 44 ms 14412 KB Output is correct
22 Correct 147 ms 27112 KB Output is correct
23 Correct 156 ms 25920 KB Output is correct
24 Correct 162 ms 26188 KB Output is correct
25 Correct 146 ms 29536 KB Output is correct
26 Correct 147 ms 26884 KB Output is correct
27 Correct 142 ms 25968 KB Output is correct
28 Correct 26 ms 6888 KB Output is correct
29 Correct 66 ms 14828 KB Output is correct
30 Correct 62 ms 14936 KB Output is correct
31 Correct 58 ms 15256 KB Output is correct
32 Correct 77 ms 19620 KB Output is correct