Submission #1027168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027168		_shr104	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	0 ms	344 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pf push_front
#define fi first
#define se second
const ll mod = 1e9+7, mxn = 1e5+7;
struct bridge_tree
{
    ll n, m, tdfs, cnt;
    vector<ll> tin, comp, low, h, u_dir, d_dir;
    vector<vector<ll>> up;
    vector<bool> used, is_bridge, vis;
    vector<vector<pair<ll,ll>>> g;
    vector<vector<ll>> b_tree;
    vector<pair<ll,ll>> ed;
    bridge_tree() {}
    bridge_tree(ll nn, ll mm)
    {
        n = nn; m = mm;
        tdfs = cnt = 0;
        tin.resize(n+7); comp.resize(n+7); low.resize(n+7);
        used.resize(n+7); is_bridge.resize(m+7);
        g.resize(n+7); b_tree.resize(n+7); ed.resize(m+7);
        h.resize(n+7); up.resize(n+7,vector<ll>(20));
        u_dir.resize(n+7); d_dir.resize(n+7); vis.resize(n+7);
    }
    void get_tree()
    {
        for (ll i = 1; i <= m; i++)
        {
            ll a, b; cin >> a >> b;
            g[a].pb({b,i}); g[b].pb({a,i});
            ed[i] = {a,b};
        }
    }
    void dfs(ll u, ll v)
    {
        tin[u] = low[u] = ++tdfs;
        used[u] = 1;
        for (pair<ll,ll> i : g[u])
        {
            if (i.fi != v)
            {
                if (used[i.fi]) low[u] = min(low[u], tin[i.fi]);
                else
                {
                    dfs(i.fi, u);
                    low[u] = min(low[u], low[i.fi]);
                    if (low[i.fi] > tin[u]) is_bridge[i.se] = 1;
                }
            }
        }
    }
    void decompose(ll u, ll v)
    {
        used[u] = 1; comp[u] = cnt;
        for (pair<ll,ll> i : g[u]) if (!is_bridge[i.se] && !used[i.fi]) decompose(i.fi,u);
    }
    void build()
    {
        get_tree(); dfs(1,1);
        for (ll i = 1; i <= n; i++) used[i] = 0;
        for (ll i = 1; i <= n; i++) if (!used[i]) {cnt++; decompose(i,i);}
        for (ll i = 1; i <= m; i++)
        {
            if (is_bridge[i])
            {
                b_tree[comp[ed[i].fi]].pb(comp[ed[i].se]);
                b_tree[comp[ed[i].se]].pb(comp[ed[i].fi]);
            }
        }
        // g.clear(); ed.clear(); used.clear(); is_bridge.clear(); 
        // tin.clear(); comp.clear(); low.clear(); 
    }
    void dfs_lca(ll u, ll v)
    {
        vis[u] = 1;
        for (ll i : b_tree[u])
        {
            if (i != v)
            {
                h[i] = h[u]+1; up[i][0] = u;
                dfs(i,u);
            }
        }
    }
    void build_lca()
    {
        for (ll i = 1; i <= cnt; i++) if (vis[i]) dfs_lca(i,i);
        for (ll i = 1; i <= cnt; i++)
        {
            for (ll j = 1; j <= 19; j++) up[i][j] = up[up[i][j-1]][j-1];
        }
    }
    ll lca(ll a, ll b)
    {
        if (h[a] != h[b])
        {
            if (h[a] < h[b]) swap(a,b);
            ll k = h[a]-h[b];
            for (ll i = __lg(k); i >= 0; i--)
            {
                if (k >> i & 1) a = up[a][i];
            }
        }
        if (a == b) return a;
        for (ll i = 19; i >= 0; i--) 
        {
            if (up[a][i] != up[b][i]) {a = up[a][i]; b = up[b][i];}
        }
        return up[a][0];
    }
    void update(ll x, ll y)
    {
        x = comp[x]; y = comp[y];
        ll l = lca(x, y);
        u_dir[x]++; u_dir[l]--;
        d_dir[y]++; d_dir[l]--;
    }
    void full_update(ll u, ll v)
    {
        for (ll i : b_tree[u])
        {
            if (i != v) 
            {
                full_update(i,u);
                u_dir[u] += u_dir[i];
                d_dir[u] += d_dir[i];
            }
        }
    }
};
char ans[mxn];
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // freopen("test.inp","r",stdin); freopen("test.out","w",stdout); freopen("test.err","w",stderr);
    ll n, m; cin >> n >> m;
    bridge_tree bt(n, m); bt.build();
    bt.build_lca(); 
    ll q; cin >> q;
    while (q--)
    {
        ll x, y; cin >> x >> y;
        if (bt.comp[x] == bt.comp[y]) continue;
        else bt.update(x,y);
    }
    for (ll i = 1; i <= bt.cnt; i++) bt.vis[i] = 0;
    for (ll i = 1; i <= bt.cnt; i++) if (!bt.vis[i]) bt.full_update(1,1);
    for (ll i = 1; i <= m; i++) 
    {
        if (bt.comp[bt.ed[i].fi] == bt.comp[bt.ed[i].se]) ans[i] = 'B';
        else 
        {
            if (bt.u_dir[bt.comp[bt.ed[i].fi]]) ans[i] = 'R';
            else if (bt.d_dir[bt.comp[bt.ed[i].fi]]) ans[i] = 'L';
            else ans[i] = 'B';
        }
    }
    for (ll i = 1; i <= m; i++) cout << ans[i];
}

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