Submission #1181048

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181048		trinm01	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	406 ms	71936 KiB

oneway

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ll long long
#define FOR(i, l, r) for (int i = (l); i <= (r); i++)
#define FOD(i, r, l) for (int i = (r); i >= (l); i--)
#define fi first
#define se second
#define pii pair<int, int>

const ll mod = 1e7 + 1203;
const ll MAXN = 1e5 + 5;
const ll oo = 1e18;
const ll base = 320;

int n, m, p, num[MAXN], low[MAXN], cnt, tp[MAXN], tplt, visited[MAXN], up[MAXN][20], h[MAXN], tp2[MAXN];
int len[MAXN], xuong[MAXN];
vector<int> adj[MAXN], adj2[MAXN], adj3[MAXN];
map<pii, int> cau, kq;
pii canh[MAXN];

void dfs(int u, int par)
{
    num[u] = low[u] = ++cnt;
    for (auto v : adj[u])
    {
        if (v == par)
            continue;
        if (!num[v])
        {
            // cout << u << ' ' << v << ''
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if (num[v] == low[v])
            {
                // cout << u << ' ' << v << ' ';
                cau[{u, v}] = 0;
                cau[{v, u}] = 0;
            }
        }
        else
        {
            low[u] = min(low[u], num[v]);
        }
    }
}

void dfs2(int u)
{
    visited[u] = 1;
    tp[u] = tplt;
    for (auto v : adj2[u])
    {
        if (!visited[v])
        {

            dfs2(v);
        }
    }
}

void dfs3(int u)
{
    visited[u]=1;
    for (auto v : adj3[u])
    {
        if (v == up[u][0])
            continue;
        if(visited[v]) continue;
        // cout << u << ' ' << v;
        h[v] = h[u] + 1;
        up[v][0] = u;
        FOR(j, 1, 19)
        {
            up[v][j] = up[up[v][j - 1]][j - 1];
        }
        dfs3(v);
    }
}

int lca(int u, int v)
{
    if (h[u] != h[v])
    {
        if (h[u] < h[v])
        {
            swap(u, v);
        }
        int k = h[u] - h[v];
        for (int j = 0; (1 << j) <= k; j++)
        {
            if ((k >> j) & 1)
            {
                u = up[u][j];
            }
        }
    }
    if (u == v)
    {
        return u;
    }
    int k = __lg(h[u]);
    FOD(j, k, 0)
    {
        if (up[u][j] != up[v][j])
        {
            u = up[u][j];
            v = up[v][j];
        }
    }
    return up[u][0];
}

int flen[MAXN], fxuong[MAXN];

void dfs4(int u, int par)
{
    visited[u] = 1;
    flen[u] = len[u];
    fxuong[u] = xuong[u];
    for (auto v : adj3[u])
    {
        if (v == par)
            continue;
        if (!visited[v])
        {
            // cout << u << ' ' << v << '\n';
            dfs4(v, u);
            if (flen[v] != 0)
            {
                if (h[flen[v]] < h[flen[u]])
                {
                    flen[u] = flen[v];
                }
                
                kq[{u, v}] = 2;
                kq[{v, u}] = 1;
            }
            if (fxuong[v] != 0)
            {
                if (h[fxuong[v]] < h[fxuong[u]])
                {
                    fxuong[u] = fxuong[v];
                }
                kq[{u, v}] = 1;
                kq[{v, u}] = 2;
            }
        }
    }
    if (flen[u] == u)
    {
        flen[u] = 0;
    }
    if (fxuong[u] == u)
    {
        fxuong[u] = 0;
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (fopen("oneway.INP", "r"))
    {
        freopen("oneway.INP", "r", stdin);
        freopen("oneway.OUT", "w", stdout);
    }

    cin >> n >> m;
    FOR(i, 1, m)
    {
        int u, v;
        cin >> u >> v;
        canh[i] = {u, v};
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    FOR(i, 1, n){
        if(!num[i]){
            dfs(i, i);
        }
    }

    FOR(i, 1, m)
    {
        auto [u, v] = canh[i];
        if (cau.find({u, v}) == cau.end())
        {
            // cout << u << ' ' << v << '\n';
            adj2[u].push_back(v);
            adj2[v].push_back(u);
        }
        else
        {
            cau[{u, v}]++;
            cau[{v, u}]++;
            // cout << u << ' ' << v << '\n';
        }
    }

    FOR(i, 1, n)
    {
        if (!visited[i])
        {
            tplt++;
            dfs2(i);
        }
    }

    FOR(i, 1, m)
    {
        auto [u, v] = canh[i];
        if (cau.find({u, v}) != cau.end())
        {
            // cout << u << ' ' << v << '\n';
            u = tp[u];
            v = tp[v];
            adj3[u].push_back(v);
            adj3[v].push_back(u);
        }
    }
    memset(visited, 0, sizeof visited);
    FOR(i, 1, n){
        if(!visited[i])
            dfs3(i);
    }
    // cout << tplt << ' ';
    // FOR(i, 1, n)
    // {
    //     cout << tp[i] << ' ';
    // }
    // cout << '\n';

    int p;
    cin >> p;
    FOR(i, 1, n)
    {
        len[i] = xuong[i] = i;
    }
    FOR(i, 1, p)
    {
        int u, v;
        cin >> u >> v;
        u = tp[u];
        v = tp[v];
        int g = lca(u, v);
        // cout << u << ' ' << v << ' ' << g << ' ' << '\n';
        if (h[g] < h[len[u]])
        {
            len[u] = g;
        }
        if (h[g] < h[xuong[v]])
        {
            xuong[v] = g;
        }
    }

    memset(visited, 0, sizeof visited);
    FOR(i, 1, n){
        if(!visited[i])
            dfs4(i, i);
    }

    FOR(i, 1, m)
    {
        auto [u, v] = canh[i];
        if (cau.find({u, v}) == cau.end())
        {
            cout << 'B';
        }
        else
        {
            if(cau[{u, v}]>1){
                cout << 'B';
                continue;
            }
            // cout << u << ' ' << v << '\n';
            u = tp[u];
            v = tp[v];
            if (kq.find({u, v}) == kq.end())
            {
                cout << 'B';
            }
            else if (kq[{u, v}] == 2)
            {
                cout << 'L';
            }
            else if (kq[{u, v}] == 1)
            {
                cout << 'R';
            }
            // cout << 'R';
        }
    }

    // cout << cau[{4, 1}];

    return 0;
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:168:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  168 |         freopen("oneway.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:169:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |         freopen("oneway.OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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