oj.uz

Submission #926386

# Submission time Handle Problem Language Result Execution time Memory
926386 2024-02-12T21:11:50 Z Regulus One-Way Streets (CEOI17_oneway) C++17
100 / 100
 721 ms 43400 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], dep[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]);
            if (low[v] > dfn[x]) cut[id] = 1;
        } else {
            low[x] = min(low[x], dfn[v]);
        }
    }
}

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, dep[x] = dep[pre] + 1;
    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)
{
    if (dep[x] < dep[y]) swap(x, y);
    int dif = dep[x] - dep[y];
    for (int i=LogN; i >= 0; --i)
    {
        if (dif & (1<<i))
        {
            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;
        debug(get_lca(x, y)), endl;
        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 (dep[x] < dep[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 3 ms 19032 KB Output is correct
2 Correct 3 ms 19036 KB Output is correct
3 Correct 4 ms 21280 KB Output is correct
4 Correct 4 ms 19288 KB Output is correct
5 Correct 4 ms 21284 KB Output is correct
6 Correct 4 ms 21084 KB Output is correct
7 Correct 5 ms 21336 KB Output is correct
8 Correct 4 ms 19292 KB Output is correct
9 Correct 4 ms 21084 KB Output is correct
10 Correct 4 ms 21084 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19032 KB Output is correct
2 Correct 3 ms 19036 KB Output is correct
3 Correct 4 ms 21280 KB Output is correct
4 Correct 4 ms 19288 KB Output is correct
5 Correct 4 ms 21284 KB Output is correct
6 Correct 4 ms 21084 KB Output is correct
7 Correct 5 ms 21336 KB Output is correct
8 Correct 4 ms 19292 KB Output is correct
9 Correct 4 ms 21084 KB Output is correct
10 Correct 4 ms 21084 KB Output is correct
11 Correct 32 ms 31368 KB Output is correct
12 Correct 40 ms 32604 KB Output is correct
13 Correct 46 ms 34444 KB Output is correct
14 Correct 53 ms 35408 KB Output is correct
15 Correct 55 ms 35776 KB Output is correct
16 Correct 55 ms 33616 KB Output is correct
17 Correct 65 ms 35668 KB Output is correct
18 Correct 60 ms 33620 KB Output is correct
19 Correct 56 ms 37460 KB Output is correct
20 Correct 40 ms 32860 KB Output is correct
21 Correct 38 ms 32340 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19032 KB Output is correct
2 Correct 3 ms 19036 KB Output is correct
3 Correct 4 ms 21280 KB Output is correct
4 Correct 4 ms 19288 KB Output is correct
5 Correct 4 ms 21284 KB Output is correct
6 Correct 4 ms 21084 KB Output is correct
7 Correct 5 ms 21336 KB Output is correct
8 Correct 4 ms 19292 KB Output is correct
9 Correct 4 ms 21084 KB Output is correct
10 Correct 4 ms 21084 KB Output is correct
11 Correct 32 ms 31368 KB Output is correct
12 Correct 40 ms 32604 KB Output is correct
13 Correct 46 ms 34444 KB Output is correct
14 Correct 53 ms 35408 KB Output is correct
15 Correct 55 ms 35776 KB Output is correct
16 Correct 55 ms 33616 KB Output is correct
17 Correct 65 ms 35668 KB Output is correct
18 Correct 60 ms 33620 KB Output is correct
19 Correct 56 ms 37460 KB Output is correct
20 Correct 40 ms 32860 KB Output is correct
21 Correct 38 ms 32340 KB Output is correct
22 Correct 721 ms 39236 KB Output is correct
23 Correct 650 ms 36888 KB Output is correct
24 Correct 634 ms 36992 KB Output is correct
25 Correct 690 ms 43400 KB Output is correct
26 Correct 697 ms 38676 KB Output is correct
27 Correct 668 ms 37212 KB Output is correct
28 Correct 563 ms 26448 KB Output is correct
29 Correct 640 ms 35572 KB Output is correct
30 Correct 647 ms 35816 KB Output is correct
31 Correct 653 ms 36268 KB Output is correct
32 Correct 681 ms 39248 KB Output is correct