oj.uz

Submission #675902

# Submission time Handle Problem Language Result Execution time Memory
675902 2022-12-28T10:29:30 Z danikoynov One-Way Streets (CEOI17_oneway) C++14
100 / 100
 206 ms 48076 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 = 2e5 + 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 = 22;
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

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15188 KB Output is correct
2 Correct 7 ms 15188 KB Output is correct
3 Correct 8 ms 15316 KB Output is correct
4 Correct 8 ms 15456 KB Output is correct
5 Correct 8 ms 15444 KB Output is correct
6 Correct 7 ms 15288 KB Output is correct
7 Correct 8 ms 15444 KB Output is correct
8 Correct 8 ms 15444 KB Output is correct
9 Correct 8 ms 15316 KB Output is correct
10 Correct 8 ms 15316 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15188 KB Output is correct
2 Correct 7 ms 15188 KB Output is correct
3 Correct 8 ms 15316 KB Output is correct
4 Correct 8 ms 15456 KB Output is correct
5 Correct 8 ms 15444 KB Output is correct
6 Correct 7 ms 15288 KB Output is correct
7 Correct 8 ms 15444 KB Output is correct
8 Correct 8 ms 15444 KB Output is correct
9 Correct 8 ms 15316 KB Output is correct
10 Correct 8 ms 15316 KB Output is correct
11 Correct 71 ms 19752 KB Output is correct
12 Correct 77 ms 21068 KB Output is correct
13 Correct 82 ms 22820 KB Output is correct
14 Correct 101 ms 26944 KB Output is correct
15 Correct 100 ms 28852 KB Output is correct
16 Correct 132 ms 40000 KB Output is correct
17 Correct 135 ms 42920 KB Output is correct
18 Correct 141 ms 41600 KB Output is correct
19 Correct 128 ms 44376 KB Output is correct
20 Correct 81 ms 21028 KB Output is correct
21 Correct 76 ms 21236 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15188 KB Output is correct
2 Correct 7 ms 15188 KB Output is correct
3 Correct 8 ms 15316 KB Output is correct
4 Correct 8 ms 15456 KB Output is correct
5 Correct 8 ms 15444 KB Output is correct
6 Correct 7 ms 15288 KB Output is correct
7 Correct 8 ms 15444 KB Output is correct
8 Correct 8 ms 15444 KB Output is correct
9 Correct 8 ms 15316 KB Output is correct
10 Correct 8 ms 15316 KB Output is correct
11 Correct 71 ms 19752 KB Output is correct
12 Correct 77 ms 21068 KB Output is correct
13 Correct 82 ms 22820 KB Output is correct
14 Correct 101 ms 26944 KB Output is correct
15 Correct 100 ms 28852 KB Output is correct
16 Correct 132 ms 40000 KB Output is correct
17 Correct 135 ms 42920 KB Output is correct
18 Correct 141 ms 41600 KB Output is correct
19 Correct 128 ms 44376 KB Output is correct
20 Correct 81 ms 21028 KB Output is correct
21 Correct 76 ms 21236 KB Output is correct
22 Correct 199 ms 45292 KB Output is correct
23 Correct 186 ms 43212 KB Output is correct
24 Correct 206 ms 43060 KB Output is correct
25 Correct 202 ms 48076 KB Output is correct
26 Correct 196 ms 44704 KB Output is correct
27 Correct 192 ms 43752 KB Output is correct
28 Correct 75 ms 18496 KB Output is correct
29 Correct 129 ms 21700 KB Output is correct
30 Correct 127 ms 22176 KB Output is correct
31 Correct 131 ms 22432 KB Output is correct
32 Correct 145 ms 30192 KB Output is correct