oj.uz

Submission #1098610

# Submission time Handle Problem Language Result Execution time Memory
1098610 2024-10-09T16:08:57 Z flyingkite One-Way Streets (CEOI17_oneway) C++17
100 / 100
 188 ms 52048 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
 
const ll N = 2e5 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 480;
ll n,m,p,timer=0;
vector<pll>adj[N];
struct ccjv{ll v, prv, nxt;};
vector<ccjv>g[N];
ll cmp[N], low[N], num[N], b[N], pa[N], up[N][20], dep[N], d[N], vs[N];
pll edge[N];
ll cur = 0;
vector<pll>order;
map<pll,ll>dir;
void pre_dfs(ll u, ll par){
    low[u] = num[u] = ++timer;
    for(auto x : adj[u]){
        ll v = x.F, idx = x.S;
        if(idx == par) continue;
        if(num[v]) low[u] = min(low[u], num[v]);
        else{
            pre_dfs(v, idx);
            low[u] = min(low[u], low[v]);
            if(low[v] == num[v]) {
                //cout << "bridge" << ' ' << u << ' ' << v << '\n';
                b[idx] = 1;
            }
        }
    }
}
void dfs_cmp(ll u, ll par){
    cmp[u] = cur;
    for(auto x : adj[u]){
        ll v = x.F, idx = x.S;
        if(idx == par) continue;
        if(b[idx]){
            if(cmp[v]) g[cmp[u]].pb({cmp[v], u, v}), g[cmp[v]].pb({cmp[u], v, u});
        }
        else if(!cmp[v]) dfs_cmp(v, idx);
    }
}
void dfs(ll u, ll par){
    vs[u] = 1;
    for(auto x : g[u]){
        ll v = x.v;
        if(v == par) continue;
        dfs(v, u);
        d[u] += d[v];
    }
    for(auto x : g[u]){
        ll v = x.v;
        if(v == par) continue;
        if(d[v] < 0) dir[{x.nxt, x.prv}] = 1, dir[{x.prv, x.nxt}] = -1;
        else if(d[v] > 0) dir[{x.nxt, x.prv}] = -1, dir[{x.prv, x.nxt}] = 1;
    }
}
void to_thic_cau(){  
    cin >> n >> m;
    for(int i = 1; i <= m;i++){
        ll u,v; cin >> u >> v;
        edge[i] = {u, v};
        adj[u].pb({v, i});
        adj[v].pb({u, i});
    }
    for(int i = 1; i <= n;i++) if(!num[i]) pre_dfs(i, 0);
    for(int i = 1; i <= n;i++){
        if(!cmp[i]){
            ++cur;
            dfs_cmp(i, 0);
        }
    }
    cin >> p;
    for(int i = 1; i <= p;i++){
        ll a,b; cin >> a >> b;
        a = cmp[a], b = cmp[b];
        d[a]--, d[b]++;
    }
    for(int i = 1; i <= n;i++){
        if(!vs[i]) dfs(i, 0);
    }
    for(int i = 1; i <= m;i++){
        if(!b[i]){
            cout << 'B';
        }
        else{
            if(!dir[{edge[i].F, edge[i].S}]) cout << 'B';
            else if(dir[{edge[i].F, edge[i].S}] == 1) cout << 'R';
            else cout << 'L';
        }
    }
    cout << '\n';
}
 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll tc = 1;
    //cin >> tc;
    while(tc--) to_thic_cau();
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9816 KB Output is correct
4 Correct 5 ms 10076 KB Output is correct
5 Correct 4 ms 10076 KB Output is correct
6 Correct 4 ms 9880 KB Output is correct
7 Correct 5 ms 10028 KB Output is correct
8 Correct 4 ms 10076 KB Output is correct
9 Correct 5 ms 9820 KB Output is correct
10 Correct 4 ms 9820 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9816 KB Output is correct
4 Correct 5 ms 10076 KB Output is correct
5 Correct 4 ms 10076 KB Output is correct
6 Correct 4 ms 9880 KB Output is correct
7 Correct 5 ms 10028 KB Output is correct
8 Correct 4 ms 10076 KB Output is correct
9 Correct 5 ms 9820 KB Output is correct
10 Correct 4 ms 9820 KB Output is correct
11 Correct 30 ms 20304 KB Output is correct
12 Correct 34 ms 22620 KB Output is correct
13 Correct 40 ms 24544 KB Output is correct
14 Correct 51 ms 27728 KB Output is correct
15 Correct 57 ms 28880 KB Output is correct
16 Correct 83 ms 35156 KB Output is correct
17 Correct 105 ms 41004 KB Output is correct
18 Correct 84 ms 35408 KB Output is correct
19 Correct 118 ms 43428 KB Output is correct
20 Correct 33 ms 20560 KB Output is correct
21 Correct 31 ms 20816 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9816 KB Output is correct
4 Correct 5 ms 10076 KB Output is correct
5 Correct 4 ms 10076 KB Output is correct
6 Correct 4 ms 9880 KB Output is correct
7 Correct 5 ms 10028 KB Output is correct
8 Correct 4 ms 10076 KB Output is correct
9 Correct 5 ms 9820 KB Output is correct
10 Correct 4 ms 9820 KB Output is correct
11 Correct 30 ms 20304 KB Output is correct
12 Correct 34 ms 22620 KB Output is correct
13 Correct 40 ms 24544 KB Output is correct
14 Correct 51 ms 27728 KB Output is correct
15 Correct 57 ms 28880 KB Output is correct
16 Correct 83 ms 35156 KB Output is correct
17 Correct 105 ms 41004 KB Output is correct
18 Correct 84 ms 35408 KB Output is correct
19 Correct 118 ms 43428 KB Output is correct
20 Correct 33 ms 20560 KB Output is correct
21 Correct 31 ms 20816 KB Output is correct
22 Correct 164 ms 45776 KB Output is correct
23 Correct 175 ms 42496 KB Output is correct
24 Correct 188 ms 42120 KB Output is correct
25 Correct 185 ms 52048 KB Output is correct
26 Correct 182 ms 45024 KB Output is correct
27 Correct 177 ms 42456 KB Output is correct
28 Correct 31 ms 16732 KB Output is correct
29 Correct 46 ms 20936 KB Output is correct
30 Correct 49 ms 21288 KB Output is correct
31 Correct 55 ms 22468 KB Output is correct
32 Correct 81 ms 31060 KB Output is correct