oj.uz

Submission #559262

# Submission time Handle Problem Language Result Execution time Memory
559262 2022-05-09T14:45:31 Z fatemetmhr One-Way Streets (CEOI17_oneway) C++17
100 / 100
 301 ms 155328 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define pb       push_back

const int maxn5 = 1e6 + 10;
const int lg    = 20;

int ty[maxn5], a[maxn5], b[maxn5], h[maxn5];
int par[lg + 2][maxn5], mn[maxn5], req[maxn5][2];
int cmp[maxn5], no = 0;
bool mark[maxn5], brsh[maxn5];
pair <int, int> e[maxn5];
vector <pair<int, int>> adj[maxn5], jda[maxn5];

inline void make_dir(int id, int u, int v){
    //cout << "dir of " << id << ' ' << u << ' ' << v << endl;
    ty[id] = 1;
    if(u == cmp[e[id].fi] && v == cmp[e[id].se])
        ty[id] = 2;
}

inline int lca(int a, int b){
    if(h[a] < h[b])
        swap(a, b);
    int d = h[a] - h[b];
    for(int i = 0; i < lg; i++) if((d >> i)&1)
        a = par[i][a];
    if(a == b)
        return a;
    for(int i = lg - 1; i >= 0; i--) if(par[i][a] != par[i][b])
        a = par[i][a], b = par[i][b];
    return par[0][a];
}

inline void dfs_det(int v, int p){
    mn[v] = h[v];
    mark[v] = true;
    for(auto [u, id] : adj[v]) if(id != p){
        if(!mark[u]){
            h[u] = h[v] + 1;
            dfs_det(u, id);
            mn[v] = min(mn[v], mn[u]);
            if(mn[u] > h[v])
                brsh[id] = true;
            //cout << "det " << v << ' ' << u  << ' ' << id << ' ' << mn[u] << ' ' << brsh[id] << endl;
        }
        else
            mn[v] = min(mn[v], mn[u]);
    }
    return;
}

inline void dfs_bor(int v){
    mark[v] = true;
    cmp[v] = no;
    //cout << "seeing " << v << ' ' << no << endl;
    for(auto [u, id] : adj[v]) if(!mark[u] && !brsh[id]){
        dfs_bor(u);
    }
}

inline void dfs_lca(int v){
    for(int i = 1; i < lg && par[i - 1][v] != -1; i++)
        par[i][v] = par[i - 1][par[i - 1][v]];
    for(auto [u, id] : jda[v]) if(u != par[0][v]){
        par[0][u] = v;
        h[u] = h[v] + 1;
        dfs_lca(u);
    }
}

inline void dfs_dir(int v){
    for(auto [u, id] : jda[v]) if(u != par[0][v]){
        dfs_dir(u);
        if(req[u][0])
            make_dir(id, u, v);
        if(req[u][1])
            make_dir(id, v, u);
        assert(!(req[u][0] && req[u][1]));

        req[v][0] += req[u][0];
        req[v][1] += req[u][1];
    }
    return;
}


int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int n, m, p; cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a, b; cin >> a >> b;
        a--; b--;
        adj[a].pb({b, i});
        adj[b].pb({a, i});
        e[i] = {a, b};
    }
    for(int i = 0; i < n; i++) if(!mark[i])
        dfs_det(i, -1);
    memset(mark, false, sizeof mark);
    for(int i = 0; i < n; i++) if(!mark[i]){
        dfs_bor(i);
        no++;
    }

    for(int i = 0; i < n; i++) for(auto [u, id] : adj[i]) if(cmp[u] != cmp[i]){
        jda[cmp[i]].pb({cmp[u], id});
        //cout << "from " << i << ' ' << u << ' '<< id << ' '<< cmp[u] << ' ' << cmp[i] << endl;
    }
    memset(par, -1, sizeof par);
    memset(h, 0, sizeof h);
    for(int i = 0; i < n; i++) if(par[0][i] == -1)
        dfs_lca(i);
    cin >> p;
    for(int i = 0; i < p; i++){
        int a, b; cin >> a >> b;
        a--; b--;
        a = cmp[a];
        b = cmp[b];
        if(a == b)
            continue;
        int c = lca(a, b);
        assert(c != -1);
        //cout << "for " << a << ' ' << b << ' ' << c << endl;
        req[a][0]++;
        req[b][1]++;
        req[c][0]--;
        req[c][1]--;
    }

    for(int i = 0; i < n; i++) if(par[0][i] == -1)
        dfs_dir(i);

    for(int i = 0; i < m; i++){
        if(!brsh[i] || ty[i] == 0)
            cout << 'B';
        else
            cout << (ty[i] == 1 ? 'L' : 'R');
    }

    cout << endl;

}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 138220 KB Output is correct
2 Correct 65 ms 138288 KB Output is correct
3 Correct 66 ms 138352 KB Output is correct
4 Correct 65 ms 138328 KB Output is correct
5 Correct 64 ms 138444 KB Output is correct
6 Correct 66 ms 138264 KB Output is correct
7 Correct 68 ms 138384 KB Output is correct
8 Correct 67 ms 138436 KB Output is correct
9 Correct 66 ms 138316 KB Output is correct
10 Correct 64 ms 138260 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 138220 KB Output is correct
2 Correct 65 ms 138288 KB Output is correct
3 Correct 66 ms 138352 KB Output is correct
4 Correct 65 ms 138328 KB Output is correct
5 Correct 64 ms 138444 KB Output is correct
6 Correct 66 ms 138264 KB Output is correct
7 Correct 68 ms 138384 KB Output is correct
8 Correct 67 ms 138436 KB Output is correct
9 Correct 66 ms 138316 KB Output is correct
10 Correct 64 ms 138260 KB Output is correct
11 Correct 100 ms 143664 KB Output is correct
12 Correct 112 ms 144280 KB Output is correct
13 Correct 116 ms 145096 KB Output is correct
14 Correct 126 ms 146372 KB Output is correct
15 Correct 127 ms 147144 KB Output is correct
16 Correct 138 ms 149516 KB Output is correct
17 Correct 162 ms 151136 KB Output is correct
18 Correct 138 ms 149780 KB Output is correct
19 Correct 160 ms 152268 KB Output is correct
20 Correct 105 ms 144056 KB Output is correct
21 Correct 99 ms 144436 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 138220 KB Output is correct
2 Correct 65 ms 138288 KB Output is correct
3 Correct 66 ms 138352 KB Output is correct
4 Correct 65 ms 138328 KB Output is correct
5 Correct 64 ms 138444 KB Output is correct
6 Correct 66 ms 138264 KB Output is correct
7 Correct 68 ms 138384 KB Output is correct
8 Correct 67 ms 138436 KB Output is correct
9 Correct 66 ms 138316 KB Output is correct
10 Correct 64 ms 138260 KB Output is correct
11 Correct 100 ms 143664 KB Output is correct
12 Correct 112 ms 144280 KB Output is correct
13 Correct 116 ms 145096 KB Output is correct
14 Correct 126 ms 146372 KB Output is correct
15 Correct 127 ms 147144 KB Output is correct
16 Correct 138 ms 149516 KB Output is correct
17 Correct 162 ms 151136 KB Output is correct
18 Correct 138 ms 149780 KB Output is correct
19 Correct 160 ms 152268 KB Output is correct
20 Correct 105 ms 144056 KB Output is correct
21 Correct 99 ms 144436 KB Output is correct
22 Correct 301 ms 152348 KB Output is correct
23 Correct 258 ms 150812 KB Output is correct
24 Correct 213 ms 151040 KB Output is correct
25 Correct 249 ms 155328 KB Output is correct
26 Correct 252 ms 151924 KB Output is correct
27 Correct 239 ms 150860 KB Output is correct
28 Correct 93 ms 142448 KB Output is correct
29 Correct 124 ms 144964 KB Output is correct
30 Correct 125 ms 145292 KB Output is correct
31 Correct 124 ms 145108 KB Output is correct
32 Correct 148 ms 148464 KB Output is correct