oj.uz

Submission #1027215

# Submission time Handle Problem Language Result Execution time Memory
1027215 2024-07-19T02:09:34 Z coldbr3w One-Way Streets (CEOI17_oneway) C++17
60 / 100
 3000 ms 44352 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;
struct ccjv{ll v, prv, nxt;};
vector<pll>adj[N];
vector<ccjv>g[N];
ll cmp[N], low[N], num[N], b[N], pa[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, ll b){
    if(u == b){
        for(auto x : order){
            dir[{x.F, x.S}] = 1;
            dir[{x.S, x.F}] = -1;
        }
    }
    for(auto x : g[u]){
        ll v = x.v;
        if(v == par) continue;
        order.pb({x.prv, x.nxt});
        dfs(v, u, b);
        order.pop_back();
    }
}
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;
        dfs(cmp[a], 0, cmp[b]);
        order.clear();
    }
    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 2 ms 12376 KB Output is correct
2 Correct 2 ms 12380 KB Output is correct
3 Correct 2 ms 12468 KB Output is correct
4 Correct 3 ms 12636 KB Output is correct
5 Correct 6 ms 12632 KB Output is correct
6 Correct 2 ms 12380 KB Output is correct
7 Correct 6 ms 12636 KB Output is correct
8 Correct 4 ms 12632 KB Output is correct
9 Correct 3 ms 12380 KB Output is correct
10 Correct 2 ms 12380 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12376 KB Output is correct
2 Correct 2 ms 12380 KB Output is correct
3 Correct 2 ms 12468 KB Output is correct
4 Correct 3 ms 12636 KB Output is correct
5 Correct 6 ms 12632 KB Output is correct
6 Correct 2 ms 12380 KB Output is correct
7 Correct 6 ms 12636 KB Output is correct
8 Correct 4 ms 12632 KB Output is correct
9 Correct 3 ms 12380 KB Output is correct
10 Correct 2 ms 12380 KB Output is correct
11 Correct 26 ms 21984 KB Output is correct
12 Correct 31 ms 23888 KB Output is correct
13 Correct 45 ms 25428 KB Output is correct
14 Correct 65 ms 29264 KB Output is correct
15 Correct 76 ms 29904 KB Output is correct
16 Correct 69 ms 35408 KB Output is correct
17 Correct 886 ms 44352 KB Output is correct
18 Correct 328 ms 35412 KB Output is correct
19 Correct 975 ms 44088 KB Output is correct
20 Correct 46 ms 21460 KB Output is correct
21 Correct 31 ms 21840 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12376 KB Output is correct
2 Correct 2 ms 12380 KB Output is correct
3 Correct 2 ms 12468 KB Output is correct
4 Correct 3 ms 12636 KB Output is correct
5 Correct 6 ms 12632 KB Output is correct
6 Correct 2 ms 12380 KB Output is correct
7 Correct 6 ms 12636 KB Output is correct
8 Correct 4 ms 12632 KB Output is correct
9 Correct 3 ms 12380 KB Output is correct
10 Correct 2 ms 12380 KB Output is correct
11 Correct 26 ms 21984 KB Output is correct
12 Correct 31 ms 23888 KB Output is correct
13 Correct 45 ms 25428 KB Output is correct
14 Correct 65 ms 29264 KB Output is correct
15 Correct 76 ms 29904 KB Output is correct
16 Correct 69 ms 35408 KB Output is correct
17 Correct 886 ms 44352 KB Output is correct
18 Correct 328 ms 35412 KB Output is correct
19 Correct 975 ms 44088 KB Output is correct
20 Correct 46 ms 21460 KB Output is correct
21 Correct 31 ms 21840 KB Output is correct
22 Execution timed out 3072 ms 40416 KB Time limit exceeded
23 Halted 0 ms 0 KB -