제출 #715729

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
715729		Valera_Grinenko	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	158 ms	26248 KiB

oneway

//#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
*/

컴파일 시 표준 에러 (stderr) 메시지

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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40