Submission #1244039

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244039		Born_To_Laugh	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	2 ms	5184 KiB

oneway

// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(Lotus) Lotus.begin(), Lotus.end()
using namespace std;
typedef long long ll;
[[maybe_unused]] const ll MOD = 998244353, INF = 1e9 + 7;
#define int ll
const int maxn = 1e5 + 10;
int n, m;
bool isbridge[maxn], ismulti[maxn];
int tin[maxn], low[maxn], comp[maxn];
int binlift[maxn][20];
vector<pair<int,int>> adj[maxn];
vector<int> bcadj[maxn];
int sum1[maxn], sum2[maxn];
int dep[maxn];
pair<int,int> edges[maxn];
map<pair<int,int>, int> mp;
/*
sum1 > 0 => up
sum2 > 0 => down
*/
int id = 0;
void tarjan(int a, int par){
    tin[a] = low[a] = ++id;
    for(auto &edge: adj[a]){
        int elm = edge.first;
        if(elm == par)continue;
        if(!tin[elm]){
            tarjan(elm, a);
            low[a] = min(low[a], low[elm]);
            if(low[elm] == tin[elm] && !ismulti[edge.second]){
                isbridge[edge.second] = 1;
                // cout <<edge.second << " cc\n";
            }
        }
        else low[a] = min(low[a], tin[elm]);
    }
}
void dfsmark(int a, int par){
    comp[a] = id;
    for(auto &edge: adj[a]){
        int elm = edge.first;
        if(elm == par || comp[elm] || isbridge[edge.second])continue;
        dfsmark(elm, a);
    }
}
void dfsbctree(int a, int par){
    for(auto &elm: bcadj[a]){
        if(elm == par)continue;
        dep[elm] = dep[a] + 1;
        binlift[elm][0] = a;
        for(int i=1; i<=n; ++i){
            binlift[elm][i] = binlift[binlift[elm][i-1]][i-1];
        }
        dfsbctree(elm, a);
        sum1[a] += sum1[elm];
        sum2[a] += sum2[elm];
    }
}
int lca(int a, int b){
    if(dep[a] < dep[b])swap(a, b);
    int k = dep[a] - dep[b];
    for(int i=0; i<20; ++i){
        if(k & (1 << i))a = binlift[a][i];
    }
    if(a == b)return a;
    for(int i=19; i>=0; --i){
        if(binlift[a][i] != binlift[b][i]){
            a = binlift[a][i];
            b = binlift[b][i];
        }
    }
    return binlift[a][0];
}
void dfscalans(int a, int par){
    for(auto &elm: bcadj[a]){
        if(elm == par)continue;
        dfscalans(elm, a);
        sum1[a] += sum1[elm];
        sum2[a] += sum2[elm];
    }
}
map<int, vector<int>> pos;
void solve(){
    cin >> n >> m;
    for(int i=1; i<=m; ++i){
        int a, b;cin >> a >> b;
        adj[a].push_back({b, i});
        adj[b].push_back({a, i});
        edges[i] = {a, b};
        pos[{min(a, b) << 32 | max(a, b)}].push_back(i);
    }
    for(auto &elm: pos){
        if(elm.second.size() > 1){
            for(auto &sth: elm.second){
                ismulti[sth] = 1;
            }
        }
    }
    tarjan(1, -1);
    id = 0;
    for(int i=1; i<=n; ++i){
        if(!comp[i]){
            id++;
            dfsmark(i, -1);
        }
    }
    for(int i=1; i<=m; ++i){
        if(!isbridge[i])continue;
        int a = comp[edges[i].first];
        int b = comp[edges[i].second];
        bcadj[a].push_back(b);
        bcadj[b].push_back(a);
    }
    dfsbctree(1, -1);
    int q;cin >> q;
    while(q--){
        int a, b;cin >> a >> b;
        a = comp[a];
        b = comp[b];
        int c = lca(a, b);
        sum1[a]++;
        sum1[c]--;
        sum2[b]++;
        sum2[c]--;
    }
    dfscalans(1, -1);
    for(int i=1; i<=m; ++i){
        if(!isbridge[i]){
            cout << "B";
            continue;
        }
        int a = edges[i].first;
        int b = edges[i].second;
        a = comp[a];b = comp[b];
        bool swapped = 0;
        if(dep[a] < dep[b]){
            swap(a, b);
            swapped = 1;
        }
        bool dir;
        if(sum1[a] > 0){
            dir = 1;//up
        }
        else if(sum2[a] > 0){
            dir = 0;//down
        }
        else{
            cout << "B";
            continue;
        }
        if(dir ^ swapped){
            cout << "R";
        }
        else{
            cout << "L";
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}

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