oj.uz

답안 #715729

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
715729 2023-03-27T16:59:13 Z Valera_Grinenko One-Way Streets (CEOI17_oneway) C++17
100 / 100
 158 ms 26248 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());

template<typename Edge>
class GraphIterator {
public:
    class OutgoingEdges {
    public:
        OutgoingEdges(const GraphIterator *g, int l, int r): g(g), l(l), r(r) {
        }

        const Edge* begin() const {
            if (l == r) {
                return 0;
            }
            return &g->prepared_edges[l];
        }

        const Edge* end() const {
            if (l == r) {
                return 0;
            }
            return &g->prepared_edges[r];
        }

    private:
        int l, r;
        const GraphIterator *g;
    };

    void clear() {
        prepared_edges.clear();
        edges.clear();
        start.clear();
        prepared = false;
    }

    void add_edge(int from, const Edge &e) {
        assert(!prepared && from >= 0);
        edges.push_back({from, e});
    }

    void prepare() {
        assert(!prepared);
        int n = 0;
        for (const auto &e : edges) {
            n = max(n, e.first);
        }
        n += 2;
        start.resize(n);
        for (const auto &e : edges) {
            ++start[e.first + 1];
        }
        for (int i = 1; i < n; ++i) {
            start[i] += start[i - 1];
        }
        prepared_edges.resize(edges.size() + 1);
        auto counter = start;
        for (const auto &e : edges) {
            prepared_edges[counter[e.first]++] = e.second;
        }
        prepared = true;
    }

    OutgoingEdges operator [] (int from) const {
        assert(prepared);
        if (from < 0 || from + 1 >= start.size()) {
            return {this, 0, 0};
        }
        return {this, start[from], start[from + 1]};
    }

private:
    vector<Edge> prepared_edges;
    vector<pair<int, Edge>> edges;
    vector<int> start;
    bool prepared = false;
};

struct bridges_two_edge_connected_components {
    static const int max_n = 2e5 + 42;
    int m = 0;
    GraphIterator<pair<int, int> > g;
    vector<bool> visited, is_bridge;
    vector<int> tin, low;
    int timer;
    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.add_edge(a, {b, m});
        g.add_edge(b, {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) {
        g.prepare();
        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;
    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
*/

Compilation message

oneway.cpp: In instantiation of 'GraphIterator<Edge>::OutgoingEdges GraphIterator<Edge>::operator[](int) const [with Edge = std::pair<int, int>]':
oneway.cpp:187:28:   required from here
oneway.cpp:152:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |         if (from < 0 || from + 1 >= start.size()) {
      |                         ~~~~~~~~~^~~~~~~~~~~~~~~
oneway.cpp: In instantiation of 'GraphIterator<Edge>::OutgoingEdges::OutgoingEdges(const GraphIterator<Edge>*, int, int) [with Edge = std::pair<int, int>]':
oneway.cpp:153:31:   required from 'GraphIterator<Edge>::OutgoingEdges GraphIterator<Edge>::operator[](int) const [with Edge = std::pair<int, int>]'
oneway.cpp:187:28:   required from here
oneway.cpp:113:30: warning: 'GraphIterator<std::pair<int, int> >::OutgoingEdges::g' will be initialized after [-Wreorder]
  113 |         const GraphIterator *g;
      |                              ^
oneway.cpp:112:13: warning:   'int GraphIterator<std::pair<int, int> >::OutgoingEdges::l' [-Wreorder]
  112 |         int l, r;
      |             ^
oneway.cpp:94:9: warning:   when initialized here [-Wreorder]
   94 |         OutgoingEdges(const GraphIterator *g, int l, int r): g(g), l(l), r(r) {
      |         ^~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 3 ms 2772 KB Output is correct
4 Correct 3 ms 2772 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 2772 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 3 ms 2772 KB Output is correct
4 Correct 3 ms 2772 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 2772 KB Output is correct
9 Correct 2 ms 2772 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct
11 Correct 33 ms 10436 KB Output is correct
12 Correct 33 ms 12060 KB Output is correct
13 Correct 38 ms 14832 KB Output is correct
14 Correct 56 ms 18808 KB Output is correct
15 Correct 52 ms 20156 KB Output is correct
16 Correct 97 ms 22688 KB Output is correct
17 Correct 82 ms 23888 KB Output is correct
18 Correct 87 ms 22716 KB Output is correct
19 Correct 96 ms 24788 KB Output is correct
20 Correct 37 ms 13744 KB Output is correct
21 Correct 34 ms 13500 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 3 ms 2772 KB Output is correct
4 Correct 3 ms 2772 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 2772 KB Output is correct
9 Correct 2 ms 2772 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct
11 Correct 33 ms 10436 KB Output is correct
12 Correct 33 ms 12060 KB Output is correct
13 Correct 38 ms 14832 KB Output is correct
14 Correct 56 ms 18808 KB Output is correct
15 Correct 52 ms 20156 KB Output is correct
16 Correct 97 ms 22688 KB Output is correct
17 Correct 82 ms 23888 KB Output is correct
18 Correct 87 ms 22716 KB Output is correct
19 Correct 96 ms 24788 KB Output is correct
20 Correct 37 ms 13744 KB Output is correct
21 Correct 34 ms 13500 KB Output is correct
22 Correct 143 ms 23888 KB Output is correct
23 Correct 131 ms 22668 KB Output is correct
24 Correct 131 ms 22768 KB Output is correct
25 Correct 123 ms 26248 KB Output is correct
26 Correct 145 ms 23596 KB Output is correct
27 Correct 158 ms 22824 KB Output is correct
28 Correct 44 ms 7612 KB Output is correct
29 Correct 57 ms 13388 KB Output is correct
30 Correct 52 ms 13532 KB Output is correct
31 Correct 50 ms 13840 KB Output is correct
32 Correct 75 ms 17764 KB Output is correct