제출 #1205983

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1205983		yassia	One-Way Streets (CEOI17_oneway)	C++20	60 / 100	3096 ms	43988 KiB

oneway

#ifndef local
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#endif

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

using namespace std;
using namespace __gnu_pbds;
using ll = long long;
#define int ll

using str = string;
using pll = pair<int,int>;
using ld = long double;

auto sd = std::chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rnd(sd);
const ll maxn = 300000;
char ans[maxn];
int comp[maxn];
bool use[maxn];
int h[maxn];
int f[maxn];
int pr[maxn];
int dp[maxn];
set<pll> edges;
int cnt =0 ;
vector<int> r;
vector<vector<int>> g;
map<pair<int,int>, int> cn;
int CNT_comp = 0;
void dfs(int v, int p) {
    use[v] = 1;
    f[v] = h[v];
    if (p != -1){
        h[v] = h[p]+1;
        f[v] = h[p]+1;
    }
    r.emplace_back(v);
    for (auto u : g[v]) {
        if (u != p){
            if (use[u]){
                f[v] = min(f[v], h[u]);
            }
            else {
                ll pre_sz = (int)r.size();
                dfs(u, v);
                f[v] = min(f[u], f[v]);
                if (h[v] < f[u] && cn[{min(u,v),max(u,v)}]==1){
                    CNT_comp++;
                    while ((ll)r.size()>pre_sz){
                        comp[r.back()]=CNT_comp;
                        r.pop_back();
                    }
                }
            }
        }
    }
}
map<pll,pll> K;
void dfs(int v, int p, vector<vector<int>>&g1){
    pr[v]= p;
    if (p!=-1){
        dp[v] = dp[p]+1;
    }
    else {
        dp[v] = 1;
    }
    for (auto u : g1[v]){
        if (u != p) {
            dfs(u, v, g1);
        }
    }
}
void solve1() {
    int n, m;
    cin >> n >> m;
    g.resize(n+1);
    vector<pair<ll,ll>> ed;
    map<pair<int,int>, int> idx;
    for (int i =0; i <m;i++){
        int u,v;
        cin>>u>>v;
        idx[{u,v}]=i;
        ed.emplace_back(u, v);
        if (u>v)swap(u,v);
        g[u].emplace_back(v);
        g[v].emplace_back(u);
        cn[{u,v}]++;
        ans[i] = 'B';
    }
    for (int i = 1; i <= n; i++){
        if (!use[i]){
            dfs(i, -1);
            ++CNT_comp;
            while (!r.empty()){
                comp[r.back()]=CNT_comp;
                r.pop_back();
            }
        }
    }
    vector<vector<ll>> g1(n+1);

    for (int i = 0; i < m; i++) {
        int u = ed[i].first;
        int v = ed[i].second;
        if (comp[u]!=comp[v]){
            g1[comp[u]].emplace_back(comp[v]);
            g1[comp[v]].emplace_back(comp[u]);
            K[{comp[u], comp[v]}]={u,v};
        }
    }
    for (int i = 1; i <= CNT_comp; i++){
        if (!dp[i]){
            dfs(i, -1, g1);
        }
    }
    int p;
    cin >> p;
    for (int i = 0; i < p; i++) {
        int a,b;
        cin >> a >> b;
        if (comp[a]==comp[b]) {
            continue;
        }
        a = comp[a];
        b = comp[b];
        while (dp[b] > dp[a]) {
                if (K.find({pr[b],b})==K.end()){
                    auto [u, v] = K[{b, pr[b]}];
                    ans[idx[{u, v}]] = 'L';
                }else {
                    auto [u, v] = K[{pr[b], b}];
                    ans[idx[{u, v}]] = 'R';
                }
                b = pr[b];
        }
        while (dp[a]> dp[b]){
            if (K.find({a, pr[a]})==K.end()){
                auto [u, v]=K[{pr[a], a}];
                ans[idx[{u, v}]] = 'L';
            }
            else {
                auto [u,v] = K[{a, pr[a]}];
                ans[idx[{u,v}]] = 'R';
            }
            a = pr[a];
        }
        while (a != b) {
            if (K.find({a, pr[a]})==K.end()) {
                auto [u, v]=K[{pr[a], a}];
                ans[idx[{u, v}]] = 'L';
            }
            else {
                auto [u,v] = K[{a, pr[a]}];
                ans[idx[{u,v}]] = 'R';
            }
            a = pr[a];
            if (K.find({pr[b],b})==K.end()){
                auto [u, v] = K[{b, pr[b]}];
                ans[idx[{u, v}]] = 'L';
            }else {
                auto [u, v] = K[{pr[b], b}];
                ans[idx[{u, v}]] = 'R';
            }
            b = pr[b];
        }
    }
    str anss;
    for (int i = 0; i < m; i++){
        anss.push_back(ans[i]);
    }
    cout<<anss;


}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef local
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    cout<<fixed<<setprecision(4);
    int t1=1;
    while (t1) t1--, solve1();
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 0 / 40