Submission #1027262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027262		_shr104	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	1 ms	860 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;
ll id[mxn], dir[mxn];
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<pair<ll,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.se != v)
            {
                if (used[i.fi]) low[u] = min(low[u], tin[i.fi]);
                else
                {
                    dfs(i.fi, i.se);
                    if (low[i.fi] == tin[i.fi]) is_bridge[i.se] = 1;
                    low[u] = min(low[u], low[i.fi]);
                }
            }
        }
    }
    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();
        for (ll i = 1; i <= n; i++) if (!used[i]) dfs(i,-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 (comp[ed[i].fi] != comp[ed[i].se])
            {
                b_tree[comp[ed[i].fi]].pb({comp[ed[i].se],i});
                b_tree[comp[ed[i].se]].pb({comp[ed[i].fi],-i});
            }
        }
        // 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 (pair<ll,ll> i : b_tree[u])
        {
            if (i.fi != v)
            {
                h[i.fi] = h[u]+1; up[i.fi][0] = u;
                dfs_lca(i.fi,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);
        // cerr << x << ' ' << l << ' ' << y << '\n';
        u_dir[x]++; u_dir[l]--;
        d_dir[y]++; d_dir[l]--;
    }
    void full_update(ll u, ll v)
    {
        vis[u] = 1; 
        for (pair<ll,ll> i : b_tree[u])
        {
            if (i.fi != v && !vis[i.fi]) 
            {
                full_update(i.fi,u);
                u_dir[u] += u_dir[i.fi];
                d_dir[u] += d_dir[i.fi];
                id[i.fi] = i.se;
            }
        }
    }
};
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;
        bt.update(x,y);
    }
    // cerr << bt.cnt << '\n';
    // for (ll i = 1; i <= n; i++) cerr << bt.comp[i] << ' ';
    // cerr << '\n';
    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(i,i);
    for (ll i = 1; i <= n; i++)
    {
        if (bt.u_dir[i] && bt.d_dir[i]) continue;
        ll idx = id[i];
        // cerr << i << ' ' << idx << '\n';
        if (bt.u_dir[i]) 
        {
            // cerr << "U" << '\n';
            if (idx > 0) dir[idx] = 1; 
            else dir[-idx] = -1;
        }
        if (bt.d_dir[i])
        {
            // cerr << "D" << '\n';
            if (idx > 0) dir[idx] = -1; 
            else dir[-idx] = 1;
        }
    }
    for (ll i = 1; i <= m; i++) 
    {
        if (dir[i] < 0) cout << "R";
        else if (dir[i] > 0) cout << "L";
        else cout << "B";
    }
}

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