oj.uz

Submission #926388

# Submission time Handle Problem Language Result Execution time Memory
926388 2024-02-12T21:13:48 Z Regulus One-Way Streets (CEOI17_oneway) C++17
100 / 100
 124 ms 38908 KB 
#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(false);cin.tie(0);
#define debug(x) cerr << #x << " = " << (x) << ' '
#define bug(x) cerr << (x) << ' '
#define endl cerr << '\n'
#define all(v) (v).begin(), (v).end()
#define SZ(v) (ll)(v).size()
#define lowbit(x) (x)&-(x)
#define pb emplace_back
#define F first
#define S second
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

const int N = 1e5+5;
const int LogN = 17;
int dfn[N], low[N], timer, tag[LogN+5][N], tin[N],
    tout[N], anc[LogN+5][N];
pll e[N];
bool cut[N];
vector<pll> g[N];
vector<int> tr[N];

inline void tarjan(int x, int pid)
{
    dfn[x] = low[x] = ++timer;
    for (auto e : g[x])
    {
        int v = e.F, id = e.S;
        if (id == pid) continue;
        if (!dfn[v])
        {
            tarjan(v, id);
            tr[x].pb(v), tr[v].pb(x);
            low[x] = min(low[x], low[v]);
        } else {
            low[x] = min(low[x], dfn[v]);
        }
        if (low[v] > dfn[x]) cut[id] = 1;
    }
}

inline bool is_anc(int x, int y)
{ return tin[x] < tin[y] && tout[y] < tout[x]; }

inline void dfs(int x, int pre)
{
    tin[x] = ++timer, anc[0][x] = pre;
    for (int v : tr[x]) if (v != pre) dfs(v, x);
    tout[x] = ++timer;
}

inline int get_lca(int x, int y)
{
    if (is_anc(x, y)) return x;
    if (is_anc(y, x)) return y;
    for (int i=LogN; i >= 0; --i)
        if (anc[i][x] && !is_anc(anc[i][x], y)) x = anc[i][x];
    return anc[0][x];
}

inline void update(int x, int y, int c)
{
    for (int i=LogN; i >= 0; --i)
    {
        if (anc[i][x] && !is_anc(anc[i][x], y))
            tag[i][x] |= c, x = anc[i][x];
    }
}

int main(void)
{ IO
    int n, i, m, Q;
    
    cin >> n >> m;
    for (i=1; i <= m; ++i)
    {
        int x, y; cin >> x >> y, e[i] = {x, y};
        g[x].pb(y, i), g[y].pb(x, i);
    }
    
    for (i=1; i <= n; ++i)
    {
        if (!dfn[i])
        {
            tarjan(i, 0);
            dfs(i, 0);
        }
    }
    for (i=1; i <= LogN; ++i)
        for (int j=1; j <= n; ++j) anc[i][j] = anc[i-1][anc[i-1][j]];
    
    cin >> Q;
    do {
        int x, y; cin >> x >> y;
        if (x == y) continue;
        int tmp = get_lca(x, y);
        update(x, tmp, 1), update(y, tmp, 2);
    } while (--Q);
    for (i=LogN; i > 0; --i)
    {
        for (int j=1; j <= n; ++j)
        {
            tag[i-1][j] |= tag[i][j];
            tag[i-1][anc[i-1][j]] |= tag[i][j];
        }
    }
    
    for (i=1; i <= m; ++i)
    {
        if (!cut[i]) cout << "B";
        else {
            int x = e[i].F, y = e[i].S;
            if (tin[x] < tin[y]) swap(x, y);
            if (tag[0][x] == 3) assert(0);
            if (tag[0][x] == 1)
            {
                if (x == e[i].F) cout << "R";
                else cout << "L";
            } else if (tag[0][x] == 2) {
                if (x == e[i].F) cout << "L";
                else cout << "R";
            } else {
                cout << "B";
            }
        }
    }
    cout << '\n';


    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16984 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3 ms 19292 KB Output is correct
4 Correct 3 ms 19292 KB Output is correct
5 Correct 3 ms 21084 KB Output is correct
6 Correct 3 ms 21080 KB Output is correct
7 Correct 4 ms 21084 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 3 ms 19036 KB Output is correct
10 Correct 3 ms 19036 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16984 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3 ms 19292 KB Output is correct
4 Correct 3 ms 19292 KB Output is correct
5 Correct 3 ms 21084 KB Output is correct
6 Correct 3 ms 21080 KB Output is correct
7 Correct 4 ms 21084 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 3 ms 19036 KB Output is correct
10 Correct 3 ms 19036 KB Output is correct
11 Correct 35 ms 30292 KB Output is correct
12 Correct 36 ms 31568 KB Output is correct
13 Correct 45 ms 33108 KB Output is correct
14 Correct 61 ms 34580 KB Output is correct
15 Correct 61 ms 34384 KB Output is correct
16 Correct 56 ms 32080 KB Output is correct
17 Correct 55 ms 34640 KB Output is correct
18 Correct 65 ms 32116 KB Output is correct
19 Correct 77 ms 36176 KB Output is correct
20 Correct 39 ms 31592 KB Output is correct
21 Correct 39 ms 31408 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16984 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3 ms 19292 KB Output is correct
4 Correct 3 ms 19292 KB Output is correct
5 Correct 3 ms 21084 KB Output is correct
6 Correct 3 ms 21080 KB Output is correct
7 Correct 4 ms 21084 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 3 ms 19036 KB Output is correct
10 Correct 3 ms 19036 KB Output is correct
11 Correct 35 ms 30292 KB Output is correct
12 Correct 36 ms 31568 KB Output is correct
13 Correct 45 ms 33108 KB Output is correct
14 Correct 61 ms 34580 KB Output is correct
15 Correct 61 ms 34384 KB Output is correct
16 Correct 56 ms 32080 KB Output is correct
17 Correct 55 ms 34640 KB Output is correct
18 Correct 65 ms 32116 KB Output is correct
19 Correct 77 ms 36176 KB Output is correct
20 Correct 39 ms 31592 KB Output is correct
21 Correct 39 ms 31408 KB Output is correct
22 Correct 117 ms 34544 KB Output is correct
23 Correct 106 ms 32028 KB Output is correct
24 Correct 88 ms 32000 KB Output is correct
25 Correct 117 ms 38908 KB Output is correct
26 Correct 124 ms 33980 KB Output is correct
27 Correct 120 ms 32084 KB Output is correct
28 Correct 33 ms 23252 KB Output is correct
29 Correct 103 ms 31068 KB Output is correct
30 Correct 101 ms 31328 KB Output is correct
31 Correct 106 ms 31884 KB Output is correct
32 Correct 97 ms 34640 KB Output is correct