제출 #675900

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
675900		danikoynov	One-Way Streets (CEOI17_oneway)	C++14	30 / 100	130 ms	33236 KiB

oneway

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 1e5 + 10;

struct edge
{
    int v, u, idx, shv, shu;

    edge(int _v = 0, int _u = 0, int _idx = 0)
    {
        v = _v;
        u = _u;
        idx = _idx;
        shv = shu = -1;
    }
} ed[maxn];

int n, m, used[maxn], in[maxn], fup[maxn], timer, bridge[maxn];
vector < pair < int, int > > g[maxn];
char ans[maxn];

void dfs(int v, int p)
{
    used[v] = 1;
    in[v] = fup[v] = ++ timer;
    for (pair < int, int > nb : g[v])
    {
        int u = nb.first;
        if (p == nb.second)
            continue;
        if (used[u])
        {
            fup[v] = min(fup[v], in[u]);
        }
        else
        {
            ans[nb.second] = 'B';
            dfs(nb.first, nb.second);
            if (fup[u] > in[v])
                bridge[nb.second] = 1;
            fup[v] = min(fup[v], fup[u]);
        }
    }
}

vector < pair < int, int > > ng[maxn];
int visit[maxn];
void decompose(int v, int idx)
{
    used[v] = idx;
    for (pair < int, int > nb : g[v])
    {
        if (bridge[nb.second])
        {
            if (used[nb.first] != 0)
            {
                ng[used[v]].push_back({used[nb.first], nb.second});
                ng[used[nb.first]].push_back({used[v], nb.second});
            }
            continue;
        }
        if (used[nb.first])
            continue;
        decompose(nb.first, idx);
    }
}

int in_time[maxn], out_time[maxn], depth[maxn], f[2 * maxn];
void euler_tour(int v, int p)
{
    in_time[v] = ++ timer;
    f[timer] = v;
    visit[v] = 1;
    for (pair < int, int > nb : ng[v])
    {
        int u = nb.first;
        if (u == p)
            continue;
        depth[u] = depth[v] + 1;
        euler_tour(u, v);
        f[++ timer] = v;
    }
    out_time[v] = timer;
}

const int maxlog = 21;
int dp[maxlog][maxn * 2], lg[maxn];

void build_sparse_table()
{
    for (int i = 1; i <= timer; i ++)
        dp[0][i] = f[i], lg[i] = lg[i / 2] + 1;

    for (int j = 1; j < lg[timer]; j ++)
    {
        for (int i = 1; i <= timer - (1 << j) + 1; i ++)
        {
            dp[j][i] = dp[j - 1][i];
            if (depth[dp[j - 1][i + (1 << (j - 1))]] < depth[dp[j][i]])
                dp[j][i] = dp[j - 1][i + (1 << (j - 1))];
        }
    }
}

int query_lca(int v, int u)
{
    int l = in_time[v], r = in_time[u];
    if (l > r)
        swap(l, r);
    int len = lg[r - l + 1] - 1;
    int ans = dp[len][l];
    if (depth[dp[len][r - (1 << len) + 1]] < depth[ans])
        ans = dp[len][r - (1 << len) + 1];
    return ans;
}

int up_add[maxn], down_add[maxn];
int up_rem[maxn], down_rem[maxn];

pair < int, int > orient_edges(int v, int p)
{
    visit[v] = 1;
    pair < int, int > sum = make_pair(up_add[v] - up_rem[v], down_add[v] - down_rem[v]);
    for (pair < int, int > nb : ng[v])
    {
        int u = nb.first;
        if (u == p)
            continue;
        pair < int, int > tr = orient_edges(u, v);
        ///cout << v << " : " << u << " : " << tr.first << " " << tr.second << endl;
        if (tr.first > 0)
        {
            ed[nb.second].shv = u;
            ed[nb.second].shu = v;
            ///cout << u << " : " << v << endl;
        }
        else if (tr.second > 0)
        {
            ed[nb.second].shv = v;
            ed[nb.second].shu = u;
        }
        sum.first += tr.first;
        sum.second += tr.second;
    }


    return sum;
}


void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i ++)
    {
        int v, u;
        cin >> v >> u;
        ed[i].v = v;
        ed[i].u = u;
        g[v].push_back({u, i});
        g[u].push_back({v, i});
    }

    for (int i = 1; i <= n; i ++)
        ans[i] = 'B';

    for (int i = 1; i <= n; i ++)
        if (!used[i])
        dfs(i, -1);

    //for (int i = 1; i <= m; i ++)
      //  if (bridge[i])
        //cout << ed[i].v << " : " << ed[i].u << endl;
    memset(used, 0, sizeof(used));

    int cnt = 0;
    for (int i = 1; i <= n; i ++)
    {
        if (!used[i])
            decompose(i, ++ cnt);
    }

    timer = 0;
    for (int i = 1; i <= cnt; i ++)
        if (!visit[i])
    euler_tour(i, 0);
    build_sparse_table();

    int q;
    cin >> q;
    for (int i = 1; i <= q; i ++)
    {
        int v, u;
        cin >> v >> u;
        v = used[v];
        u = used[u];
        int lca = query_lca(v, u);

        up_add[v] ++;
        down_add[u] ++;
        up_rem[lca] ++;
        down_rem[lca] ++;
    }

    memset(visit, 0, sizeof(visit));
    for (int i = 1; i <= n; i ++)
        if (!visit[i])
    orient_edges(i, 0);
    for (int i = 1; i <= m; i ++)
    {
        if (ed[i].shv == -1)
            cout << 'B';
        else if (ed[i].shv == used[ed[i].v])
            cout << 'R';
        else
            cout << 'L';
    }
    cout << endl;
}

int main()
{
    solve();
    return 0;
}
/**
20 23
1 15
1 16
15 16
6 5
5 16
15 5
6 10
18 20
19 18
3 4
3 10
17 20
19 20
13 14
11 9
11 12
12 2
2 11
9 8
7 8
9 10
6 8
12 13
7
13 4
2 7
16 3
17 18
17 19
8 10
10 8
*/

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