oj.uz

Submission #858474

# Submission time Handle Problem Language Result Execution time Memory
858474 2023-10-08T14:24:27 Z anarch_y One-Way Streets (CEOI17_oneway) C++17
0 / 100
 5 ms 4444 KB 
#include <bits/stdc++.h>
#pragma GCC target("popcnt")
using namespace std;
using pii = pair<int, int>;
using ll = long long;
#define all(x) begin(x), end(x)
#define pb push_back
 
const int maxn = 100005;
int n, m, q;
vector<int> adj[maxn];
int par[maxn], tin[maxn], up[maxn];
bool visited[maxn];
vector<pii> edges;
set<pii> extra;
map<pii, int> mp, bridge, out;
int ct = 0;
 
void dfs(int v, int p){
    par[v] = p; visited[v] = true;
    tin[v] = ++ct; up[v] = tin[v];
    for(auto u: adj[v]){
        if(u==p) continue;
        if(visited[u]){
            up[v] = min(up[v], tin[u]);
        }
        else{
            dfs(u, v);
            up[v] = min(up[v], up[u]);
        }
    }
    if(up[v] > tin[p]){
        bridge[{v, p}] = 1;
    }
}

void begin(){
    tin[0] = 1e9;
    for(int i=1; i<=n; i++){
        if(!visited[i]) dfs(i, 0);
    }
}

struct LCA{
    int n, rt; 
    vector<vector<int>> adj, up;
    vector<int> depth;
    LCA(int _n){
        n = _n;
        up.resize(n+1);
        for(int i=0; i<=n; i++){
            up[i].resize(20, 0);
        }
        adj.resize(n+1);
        depth.resize(n+1, 0);
    }
    void ae(int a, int b){
        adj[a].pb(b);
        adj[b].pb(a);
    }
    void dfs(int s, int p){
        depth[s] = depth[p]+1;
        up[s][0] = p;
        for(auto u: adj[s]){
            if(u==p) continue;
            dfs(u, s);
        }
    }
    void init(){
        for(int j=1; j<20; j++){
            for(int i=1; i<=n; i++){
                up[i][j] = up[up[i][j-1]][j-1];
            }
        }    
    }
    int jump(int x, int d){
        for(int i=0; i<20; i++){
            if(1<<i & d) x = up[x][i];
        }
        return x;
    }
    int lca(int a, int b){
        if(depth[a] < depth[b]) swap(a, b);
        a = jump(a, depth[a]-depth[b]);
    
        if(a==b) return a; 
    
        for(int i=19; i>=0; i--){
            if(up[a][i] != up[b][i]){
                a = up[a][i];
                b = up[b][i];
            }
        }
        return up[a][0];
    }
	int dist(int a, int b){
		int c = lca(a, b);
		int d = depth[a]+depth[b]-2*depth[c];
		return d;
	}
};
 
int main(){
    ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
    cin >> n >> m;
    for(int i=0; i<m; i++){
        int a, b; cin >> a >> b;
        edges.pb({a, b});
        if(a==b) continue;
        if(mp[{a, b}] or mp[{b, a}]){
            extra.insert({a, b});
        }    
        else{
            adj[a].pb(b); adj[b].pb(a);
            mp[{a, b}] = 1;
        }
    }
    begin();

    LCA L(n);
    for(int i=2; i<=n; i++){
        L.ae(i, par[i]);
    }
    for(int i=1; i<=n; i++){
        if(!L.depth[i]){
            L.dfs(i, 0);
        }
    }
    L.init();

    cin >> q;
    while(q--){
        int a, b; cin >> a >> b;
        if(a==b) continue;
        int c = L.lca(a, b);
        while(a != c){
            if(bridge[{a, par[a]}] == 1){
                out[{a, par[a]}] = 1;
                out[{par[a], a}] = -1;
            }
            a = par[a];
        }
        while(b != c){
            if(bridge[{b, par[b]}] == 1){
                out[{b, par[b]}] = -1;
                out[{par[b], b}] = 1;
            }
            b = par[b];
        }
    }

    for(auto p: extra){
        out[p] = 0;
    }

    for(auto p: edges){
        if(out[p]==0) cout << 'B';
        else if(out[p]==1) cout << 'R';
        else cout << 'L';
    }

}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3676 KB Output is correct
2 Correct 1 ms 3676 KB Output is correct
3 Correct 2 ms 4188 KB Output is correct
4 Correct 2 ms 4188 KB Output is correct
5 Correct 5 ms 4444 KB Output is correct
6 Correct 2 ms 4188 KB Output is correct
7 Correct 5 ms 4444 KB Output is correct
8 Correct 3 ms 4188 KB Output is correct
9 Incorrect 2 ms 4188 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3676 KB Output is correct
2 Correct 1 ms 3676 KB Output is correct
3 Correct 2 ms 4188 KB Output is correct
4 Correct 2 ms 4188 KB Output is correct
5 Correct 5 ms 4444 KB Output is correct
6 Correct 2 ms 4188 KB Output is correct
7 Correct 5 ms 4444 KB Output is correct
8 Correct 3 ms 4188 KB Output is correct
9 Incorrect 2 ms 4188 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3676 KB Output is correct
2 Correct 1 ms 3676 KB Output is correct
3 Correct 2 ms 4188 KB Output is correct
4 Correct 2 ms 4188 KB Output is correct
5 Correct 5 ms 4444 KB Output is correct
6 Correct 2 ms 4188 KB Output is correct
7 Correct 5 ms 4444 KB Output is correct
8 Correct 3 ms 4188 KB Output is correct
9 Incorrect 2 ms 4188 KB Output isn't correct
10 Halted 0 ms 0 KB -