oj.uz

답안 #675900

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
675900 2022-12-28T10:28:21 Z danikoynov One-Way Streets (CEOI17_oneway) C++14
30 / 100
 130 ms 33236 KB 
/**
 ____ ____ ____ ____ ____ ____
||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.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7764 KB Output is correct
2 Correct 4 ms 7796 KB Output is correct
3 Correct 4 ms 7860 KB Output is correct
4 Correct 6 ms 8000 KB Output is correct
5 Correct 5 ms 8020 KB Output is correct
6 Correct 5 ms 7764 KB Output is correct
7 Correct 5 ms 8148 KB Output is correct
8 Correct 5 ms 8008 KB Output is correct
9 Correct 5 ms 7764 KB Output is correct
10 Correct 5 ms 7788 KB Output is correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7764 KB Output is correct
2 Correct 4 ms 7796 KB Output is correct
3 Correct 4 ms 7860 KB Output is correct
4 Correct 6 ms 8000 KB Output is correct
5 Correct 5 ms 8020 KB Output is correct
6 Correct 5 ms 7764 KB Output is correct
7 Correct 5 ms 8148 KB Output is correct
8 Correct 5 ms 8008 KB Output is correct
9 Correct 5 ms 7764 KB Output is correct
10 Correct 5 ms 7788 KB Output is correct
11 Correct 68 ms 13364 KB Output is correct
12 Correct 94 ms 14716 KB Output is correct
13 Correct 98 ms 16484 KB Output is correct
14 Correct 113 ms 20648 KB Output is correct
15 Correct 110 ms 22488 KB Output is correct
16 Incorrect 130 ms 33236 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7764 KB Output is correct
2 Correct 4 ms 7796 KB Output is correct
3 Correct 4 ms 7860 KB Output is correct
4 Correct 6 ms 8000 KB Output is correct
5 Correct 5 ms 8020 KB Output is correct
6 Correct 5 ms 7764 KB Output is correct
7 Correct 5 ms 8148 KB Output is correct
8 Correct 5 ms 8008 KB Output is correct
9 Correct 5 ms 7764 KB Output is correct
10 Correct 5 ms 7788 KB Output is correct
11 Correct 68 ms 13364 KB Output is correct
12 Correct 94 ms 14716 KB Output is correct
13 Correct 98 ms 16484 KB Output is correct
14 Correct 113 ms 20648 KB Output is correct
15 Correct 110 ms 22488 KB Output is correct
16 Incorrect 130 ms 33236 KB Output isn't correct
17 Halted 0 ms 0 KB -