oj.uz

Submission #921295

# Submission time Handle Problem Language Result Execution time Memory
921295 2024-02-03T16:35:35 Z Lecorbio One-Way Streets (CEOI17_oneway) C++17
0 / 100
 418 ms 262144 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;

const int N = 1e6+10;
const int P = 22;

int n, m;
pair<int,int> edge[N];
vector<pair<int,int>> g[N];

int tin[N], tout[N], low[N];
bool vis[N], bridge[N];
int comp[N];
vector<pair<int,int>> gc[N];

int depth[N];
pair<int,int> parent[N];
int up[N][P+3];
int path[N][3];
int direction[N];
char label[N];


///drewo dwuspojnych
int timer = 0;
void dfs_low(int v, int p){
    vis[v] = true;
    tin[v] = low[v] = ++timer;

    for (auto u : g[v]){
        if (u.fi == p) continue;
        if (vis[u.fi]){
            low[v] = min(low[v], tin[u.fi]);
        }else{
            dfs_low(u.fi, v);
            low[v] = min(low[v], low[u.fi]);
            if (low[u.fi] > tin[v]) bridge[u.se] = true;
        }
    }
}

void components(int v, int c){
    vis[v] = true;
    comp[v] = c;
    for (auto u : g[v]){
        if (!vis[u.fi] && !bridge[u.se]){
            components(u.fi, c);
        }
    }
}


///LCA
int order = 0;
void dfs_lca(int v, int p, int idx){
    vis[v] = true;
    tin[v] = ++order;
    up[v][0] = p;
    parent[v] = {p, idx};

    for (int i=1; i<=P; i++){
        up[v][i] = up[up[v][i-1]][i-1];
    }

    for (auto u : gc[v]){
        if (u.fi != p){
            depth[u.fi] = depth[v] + 1;
            dfs_lca(u.fi, v, u.se);
        }
    }
    tout[v] = order;
}

bool is_ancestor(int u, int v){
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v){
    if (is_ancestor(u, v)) return u;
    if (is_ancestor(v, u)) return v;

    for (int i=P; i>=0; i--){
        if (!is_ancestor(up[u][i], v)) u = up[u][i];
    }
    return up[u][0];
}


///skierowanie krawedzi
void direct(int x, int z, int dir){
    if (x == z) return;
    if (direction[x] == 0){
        direction[x] = dir;
        int p = parent[x].fi;
        int idx = parent[x].se;
        int a = comp[edge[idx].fi];
        int b = comp[edge[idx].se];

        if (dir == -1){
            if (a == x && b == p) label[idx] = 'R';
            else label[idx] = 'L';
        }else{
            if (a == x && b == p) label[idx] = 'L';
            else label[idx] = 'R';
        }
        direct(p, z, dir);
    }
}


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

    cin >> n >> m;
    for (int i=0; i<m; i++){
        int a, b; cin >> a >> b;
        edge[i] = {a, b};
        g[a].push_back({b, i});
        g[b].push_back({a, i});
    }

    //drzewo dwuspojnych
    for (int i=1; i<=n; i++){
        if (!vis[i]) dfs_low(i, -1);
    }

    for (int i=1; i<=n; i++) vis[i] = false;
    int c = 1;
    for (int i=1; i<=n; i++){
        if (!vis[i]){
            components(i, c);
            c++;
        }
    }

    for (int i=0; i<m; i++){
        if (bridge[i]){
            int ca = comp[edge[i].fi];
            int cb = comp[edge[i].se];
            gc[ca].push_back({cb, i});
            gc[cb].push_back({ca, i});
        }
    }

    //lca
    for (int i=1; i<=n; i++) vis[i] = false;
    for (int i=1; i<=n; i++){
        if (!vis[i]){
            depth[i] = 1;
            dfs_lca(i, i, -1);
        }
    }

    //skierowanie krawedzi
    for (int i=0; i<m; i++) label[i] = 'B';
    vector<pair<int,int>> ord;
    int q; cin >> q;
    for (int i=0; i<q; i++){
        int a, b; cin >> a >> b;
        path[i][0] = comp[a];
        path[i][1] = comp[b];
        path[i][2] = lca(comp[a], comp[b]);
        ord.push_back({depth[path[i][2]], i});
    }

    sort(ord.begin(), ord.end());
    for (auto ele : ord){
        int a = path[ele.se][0];
        int b = path[ele.se][1];
        int lc = path[ele.se][2];
        direct(a, lc, -1);
        direct(b, lc, 1);
    }
    for (int i=0; i<m; i++) cout << label[i];

    return 0;
}
/*

5 6
1 2
1 2
4 3
2 3
1 3
5 1
2
4 5
1 3

*/

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 63836 KB Output is correct
2 Correct 15 ms 64092 KB Output is correct
3 Correct 16 ms 64092 KB Output is correct
4 Correct 15 ms 64092 KB Output is correct
5 Correct 15 ms 64092 KB Output is correct
6 Correct 16 ms 64088 KB Output is correct
7 Correct 16 ms 64092 KB Output is correct
8 Correct 14 ms 64176 KB Output is correct
9 Runtime error 418 ms 262144 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 63836 KB Output is correct
2 Correct 15 ms 64092 KB Output is correct
3 Correct 16 ms 64092 KB Output is correct
4 Correct 15 ms 64092 KB Output is correct
5 Correct 15 ms 64092 KB Output is correct
6 Correct 16 ms 64088 KB Output is correct
7 Correct 16 ms 64092 KB Output is correct
8 Correct 14 ms 64176 KB Output is correct
9 Runtime error 418 ms 262144 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 63836 KB Output is correct
2 Correct 15 ms 64092 KB Output is correct
3 Correct 16 ms 64092 KB Output is correct
4 Correct 15 ms 64092 KB Output is correct
5 Correct 15 ms 64092 KB Output is correct
6 Correct 16 ms 64088 KB Output is correct
7 Correct 16 ms 64092 KB Output is correct
8 Correct 14 ms 64176 KB Output is correct
9 Runtime error 418 ms 262144 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -