Submission #1090316

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

oneway

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 100;
const int MAX_LOG = 18;
vector<pair<int, int>> a[MAXN];
vector<pair<int, int>> bridges[MAXN];
vector<pair<int, int>> edges;
int parent[MAXN][MAX_LOG];
int tin[MAXN];
int tout[MAXN];
int components = 0;
int counter = 0;
int bridge = 0;
int num[MAXN];
int low[MAXN];
bool isBridge[MAXN];
int vis[MAXN];
int comp[MAXN];
int cnt[MAXN];
int ans[MAXN];
int inv[MAXN];
int n, m, p;
void dfs(int u, int p, int f){
    num[u] = low[u] = ++counter;
    for (auto x: a[u]){
         int v = x.first;
         if (x.second == f) continue;
         if (!num[v]){
             dfs(v, u, x.second);
             low[u] = min(low[u], low[v]);
             if (low[v] == num[v]){
                 bridge++;
                 isBridge[x.second] = true;
             }
         }
         else low[u] = min(low[u], num[v]);
    }
}
void dfs1(int u, int p){
    comp[u] = components;
    vis[u] = 1;
    for (auto v: a[u]){
         if (vis[v.first] || isBridge[v.second]) continue;
         dfs1(v.first, u);
    }
}
void dfs2(int u, int p){
    parent[u][0] = p;
    tin[u] = ++counter;
    for (auto x: bridges[u]){
         int v = x.first;
         if (v != p){
             inv[x.second] = (u != x.first);
             dfs2(v, u);
         }
    }
    tout[u] = ++counter;
}
bool Ancestor(int u, int v){
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int LCA(int u, int v){
    if (Ancestor(u, v)) return u;
    if (Ancestor(v, u)) return v;
    for (int k = MAX_LOG - 1; k >= 0; k--){
         if (!Ancestor(parent[u][k], v)){
             u = parent[u][k];
         }
    }
    return parent[u][0];
}
void pre(){
    counter = 0;
    dfs2(1, 1);
    for (int k = 1; k < MAX_LOG; k++){
         for (int i = 1; i <= components; i++){
              parent[i][k] = parent[parent[i][k - 1]][k - 1];
         }
    }
}
void dfs3(int u, int p){
    for (auto x: bridges[u]){
         int v = x.first;
         if (v == p) continue;
         dfs3(v, u);
         cnt[u] += cnt[v];
         if (cnt[v] > 0){
             ans[x.second] = 1;
         }
         else if (cnt[v] < 0){
             ans[x.second] = -1;
         }
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; i++){
         int x, y;
         cin >> x >> y;
         a[x].push_back({y, i});
         a[y].push_back({x, i});
         edges.push_back({x, y});
    }
    counter = 0;
    for (int i = 1; i <= n; i++){
        if (!num[i]){
             dfs(1, -1, -1);
        }
    }
    for (int i = 1; i <= n; i++){
         if (!vis[i]){
            components++;
            dfs1(i, -1);
         }
    }
    for (int i = 0; i < m; i++){
         if (isBridge[i]){
             bridges[comp[edges[i].first]].push_back({comp[edges[i].second], i});
             bridges[comp[edges[i].second]].push_back({comp[edges[i].first], i});
         }
    }
    pre();
    cin >> p;
    while (p--){
         int x, y;
         cin >> x >> y;
         x = comp[x];
         y = comp[y];
         int lca = LCA(x, y);
         cnt[x]++;
         cnt[y]--;
         cnt[lca] += 0;
    }
    dfs3(1, -1);
    for (int i = 0; i < m; i++){
         if (inv[i]) ans[i] *= (-1);
         if (ans[i] == -1) cout << "R";
         else if (ans[i] == 1) cout << "L";
         else cout << "B";
    }
}

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