제출 #1335860

#제출 시각아이디문제언어결과실행 시간메모리
1335860iamhereforfunOne-Way Streets (CEOI17_oneway)C++20
0 / 100
2 ms344 KiB
// Starcraft 2 enjoyer //

#include <bits/stdc++.h>

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

#define LSOne(X) ((X) & -(X))
#define int long long

const int N = 1e5 + 5;
const int M = 1e6 + 5;
const int K = 1e3 + 5;
const int LG = 60;
const int INF = 1e18 + 5;
const int B = 1000;
const int MOD = 1e9 + 7;

int n, m, q, cid, id[N], low[N], type[N], cur, binlift[N][LG], depth[N], ans[N], mxu[N], mxd[N];
bool vis[N], bridge[N], chk[N];
vector<pair<int, int>> edges, adj[N], adj2[N];

void dfs1(int c, int l)
{
    if (vis[c])
        return;
    vis[c] = 1;
    id[c] = cid;
    low[c] = cid++;
    for (auto &[i, j] : adj[c])
    {
        if (j == l)
            continue;
        if (chk[j])
        {
            low[c] = min(low[c], id[i]);
            continue;
        }
        chk[j] = 1;
        dfs1(i, j);
        low[c] = min(low[c], low[i]);
        // cout << low[i] << " " << id[i] << " " << id[c] << " " << i << " " << c << "\n";
        if (low[i] > id[c])
        {
            bridge[j] = 1;
            // cout << j + 1 << "\n";
        }
    }
    // cout << low[c] << " " << id[c] << " " << c << "\n";
}

void dfs2(int c)
{
    if (vis[c])
        return;
    type[c] = cur;
    vis[c] = 1;
    id[c] = cid;
    low[c] = cid++;
    for (auto &[i, j] : adj[c])
    {
        if (bridge[j])
            continue;
        chk[j] = 1;
        dfs2(i);
    }
}

void dfs3(int c, int p)
{
    for (auto &[i, id] : adj2[c])
    {
        if (i == p)
            continue;
        depth[i] = depth[c] + 1;
        binlift[0][i] = c;
        for (int x = 1; x < LG; x++)
        {
            binlift[x][i] = binlift[x - 1][binlift[x - 1][i]];
        }
        dfs3(i, c);
    }
}

pair<int, int> dfs4(int c, int p)
{
    pair<int, int> pr = {depth[c] + 1, 0};
    for (auto &[i, id] : adj2[c])
    {
        if (i == p)
            continue;
        pair<int, int> cur = dfs4(i, c);
        // cout << cur.first << " " << cur.second << " " << i << " " << c << "\n";
        if (cur.first <= depth[c])
        {
            if (cur.second == 1) // go up
            {
                // cout << i << " " << edges[id].first << " " << edges[id].second << "\n";
                if (type[edges[id].first] == i)
                {
                    ans[id] = 1;
                }
                else
                {
                    ans[id] = 2;
                }
            }
            else // go down
            {
                if (type[edges[id].first] == i)
                {
                    ans[id] = 2;
                }
                else
                {
                    ans[id] = 1;
                }
            }
        }
        else
        {
            ans[id] = 0;
        }
        pr = min(pr, cur);
    }
    if (mxu[c] < depth[c])
    {
        pr = min(pr, (pair<int, int>){mxu[c], 1});
    }
    if (mxd[c] < depth[c])
    {
        pr = min(pr, (pair<int, int>){mxd[c], 2});
    }
    return pr;
}

int lca(int a, int b)
{
    if (depth[a] != depth[b])
    {
        if (depth[a] < depth[b])
            swap(a, b);
        int k = depth[a] - depth[b];
        for (int x = 0; x < LG; x++)
        {
            if (k >> x & 1)
            {
                a = binlift[x][a];
            }
        }
    }
    if (a == b)
        return a;
    for (int x = LG - 1; x >= 0; x--)
    {
        if (binlift[x][a] != binlift[x][b])
        {
            a = binlift[x][a];
            b = binlift[x][b];
        }
    }
    return binlift[0][a];
}

inline void solve()
{
    cin >> n >> m;
    for (int x = 0; x < m; x++)
    {
        int a, b;
        cin >> a >> b;
        adj[a].push_back({b, x});
        adj[b].push_back({a, x});
        edges.push_back({a, b});
    }
    for (int x = 1; x <= n; x++)
    {
        if (vis[x])
            continue;
        dfs1(x, -1);
    }
    for (int x = 1; x <= n; x++)
    {
        vis[x] = 0;
    }
    for (int x = 0; x < m; x++)
    {
        chk[x] = 0;
    }
    cur = 1;
    for (int x = 1; x <= n; x++)
    {
        if (vis[x])
            continue;
        dfs2(x);
        cur++;
    }
    for (int x = 0; x < m; x++)
    {
        if (!bridge[x])
        {
            ans[x] = 0;
            continue;
        }
        // cout << edges[x].first << " " << edges[x].second << "\n";
        int a = type[edges[x].first];
        int b = type[edges[x].second];
        if (a == b)
            continue;
        adj2[a].push_back({b, x});
        adj2[b].push_back({a, x});
    }
    dfs3(1, 0);
    for (int x = 1; x < cur; x++)
    {
        mxd[x] = mxu[x] = depth[x];
    }
    cin >> q;
    for (int x = 0; x < q; x++)
    {
        int a, b, c;
        cin >> a >> b;
        a = type[a];
        b = type[b];
        c = lca(a, b);
        mxu[a] = min(mxu[a], depth[c]);
        mxd[b] = min(mxd[b], depth[c]);
    }
    // for(int x = 1; x < cur; x++)
    // {
    //     cout << mxu[x] << " " << mxd[x] << "\n";
    // }
    // cout << "\n";
    dfs4(1, 0);
    for (int x = 0; x < m; x++)
    {
        if (ans[x] == 0)
        {
            cout << 'B';
        }
        else if (ans[x] == 1)
        {
            cout << 'R';
        }
        else
        {
            cout << 'L';
        }
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int x = 1; x <= t; x++)
    {
        solve();
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...