Submission #1206116

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206116		yassia	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	499 ms	66796 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];
int sz[maxn];
int head[maxn];
int tin[maxn];
int tout[maxn];
int d[4*maxn+100];
int push[4*maxn+100];
void makepush(int v) {
    if (push[v]==0){
        return;
    }
    d[v*2] = push[v];
    d[v*2+1] = push[v];
    push[v*2+1] = push[v];
    push[v*2] =push[v];
    push[v]=0;
}
void upd(int v, int l, int r, int sl, int sr, int val){
    makepush(v);
    if (sl <= l && r <= sr){
        d[v] = val;
        push[v] = val;
        makepush(v);
        return;
    }
    else if (sr <= l || r <= sl){
        return;
    }
    makepush(v);
    upd(v*2, l,(l+r)/2, sl, sr,val);
    upd(v*2+1, (l+r)/2, r, sl, sr, val);
    d[v] = max(d[v*2],d[v*2+1]);
}
int get(int v, int l, int r, int i) {
    makepush(v);
    if(i==l && i+1==r){
        return d[v];
    }
    else if (i < l || r <= i){
        return 0;
    }
    makepush(v);
    if (i < (l+r)/2){
        return get(v*2, l, (l+r)/2, i);
    }
    else {
        return get(v*2+1, (l+r)/2,r, i);
    }
}
int timer =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;
    sz[v]++;
    if (p != -1) {
        dp[v] = dp[p]+1;
    }
    else {
        dp[v] = 1;
    }
    for (auto u : g1[v]){
        if (u != p) {
            dfs(u, v, g1);
            sz[v] += sz[u];

        }
    }
}
void hl(int v, int p, vector<vector<int>>&g1){
    int ff = -1;
    tin[v] = timer++;
    for (int i = 0; i < g1[v].size(); i++){
        int u = g1[v][i]; if (u != p && (ff == -1 || sz[u]>sz[g1[v][0]])){
            ff = 1;
            swap(g1[v][0], g1[v][i]);
        }
    }
    for (int i =0; i < g1[v].size(); i++){
        int u = g1[v][i];
        if (u != p) {
            if (i==0) head[u]= head[v];
            else head[u] = u;
            hl(u, v, g1);
        }
    }
    tout[v] = timer++;
}
bool is_anc(int u, int v){
    return (tin[u]<=tin[v] && tout[u]>=tout[v]);
}
void up(int &a, int &b, int val, bool change) {
    while (!is_anc(head[a], b)){
        if (change) upd(1, 0, timer, tin[head[a]], tin[a]+1, val);
        a = pr[head[a]];
    }
}
ll update(int a, int b, int v, bool change){
    up(a, b, v, change);
    up(b, a, v, change);
    if (!is_anc(a, b))swap(a, b);
    if (change) upd(1, 0, timer, tin[a],tin[b]+1, v);
    return a;
}

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]){
            head[i] = i;
            dfs(i, -1, g1);
            hl(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];
        int lc = update(a, b, 0, 0);
        if (a == lc) {
            int nx_b = lc;
            for (auto u : g1[lc]) {
                if (is_anc(u, b) && dp[u]>dp[lc]) nx_b = u;
            }
            update(nx_b, b, 1, 1);
        }
        else if (b == lc) {
            int nx_a = lc;
            for (auto u : g1[lc]) {
                if (is_anc(u, a) && dp[u]>dp[lc]) nx_a = u;
            }
            update(nx_a, a, 2,1);
        }
        else{
            int nx_a = lc; int nx_b = lc;
            for (auto u : g1[lc]) {
                if (is_anc(u, a) && dp[u]>dp[lc]) {
                    nx_a = u;
                }
                if (is_anc(u,b) && dp[u]>dp[lc]){
                    nx_b = u;
                }
            }
            update(nx_a, a, 2,1);
            update(nx_b, b, 1,1);
        }
    }
    for (int i = 1; i <= CNT_comp; i++){
        if (pr[i]!=-1) {
            int gt = get(1, 0, timer, tin[i]);
            if (gt == 1) {
                if (K.find({pr[i],i})==K.end()){
                    auto [u, v] = K[{i, pr[i]}];
                    ans[idx[{u, v}]] = 'L';
                }else {
                    auto [u, v] = K[{pr[i], i}];
                    ans[idx[{u, v}]] = 'R';
                }
            }
            if (gt == 2) {
                if (K.find({i, pr[i]})==K.end()) {
                    auto [u, v]=K[{pr[i], i}];
                    ans[idx[{u, v}]] = 'L';
                }
                else {
                    auto [u,v] = K[{i, pr[i]}];
                    ans[idx[{u,v}]] = 'R';
                }
            }
        }
    }

    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: 40 / 40