oj.uz

Submission #926387

# Submission time Handle Problem Language Result Execution time Memory
926387 2024-02-12T21:13:04 Z Regulus One-Way Streets (CEOI17_oneway) C++17
30 / 100
 74 ms 69740 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;
        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 (x == y) continue;
            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 3 ms 16984 KB Output is correct
2 Correct 3 ms 17240 KB Output is correct
3 Correct 3 ms 19292 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 3 ms 21084 KB Output is correct
6 Correct 3 ms 21336 KB Output is correct
7 Correct 3 ms 21084 KB Output is correct
8 Correct 3 ms 19036 KB Output is correct
9 Correct 3 ms 19036 KB Output is correct
10 Correct 4 ms 19036 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 3 ms 17240 KB Output is correct
3 Correct 3 ms 19292 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 3 ms 21084 KB Output is correct
6 Correct 3 ms 21336 KB Output is correct
7 Correct 3 ms 21084 KB Output is correct
8 Correct 3 ms 19036 KB Output is correct
9 Correct 3 ms 19036 KB Output is correct
10 Correct 4 ms 19036 KB Output is correct
11 Correct 32 ms 30300 KB Output is correct
12 Correct 38 ms 31576 KB Output is correct
13 Correct 47 ms 33116 KB Output is correct
14 Runtime error 74 ms 69740 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 3 ms 17240 KB Output is correct
3 Correct 3 ms 19292 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 3 ms 21084 KB Output is correct
6 Correct 3 ms 21336 KB Output is correct
7 Correct 3 ms 21084 KB Output is correct
8 Correct 3 ms 19036 KB Output is correct
9 Correct 3 ms 19036 KB Output is correct
10 Correct 4 ms 19036 KB Output is correct
11 Correct 32 ms 30300 KB Output is correct
12 Correct 38 ms 31576 KB Output is correct
13 Correct 47 ms 33116 KB Output is correct
14 Runtime error 74 ms 69740 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -