Submission #921315

#	Time	Username	Problem	Language	Result	Execution time	Memory
921315		Lecorbio	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	127 ms	34488 KiB

oneway

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;

const int N = 1e5+10;
const int P = 20;

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.se == p) continue;
        if (vis[u.fi]){
            low[v] = min(low[v], tin[u.fi]);
        }else{
            dfs_low(u.fi, u.se);
            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});
        }
    }
    /*
    cout << '\n';
    for (int i=1; i<=n; i++){
        cout << i << ": ";
        for (auto ele : gc[i]) cout << ele.fi << ' ';
        cout << '\n';
    }
    */

    //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, 0);
        }
    }

    //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];
    cout << '\n';

    return 0;
}
/*

10 10
7 6
4 1
6 6
10 10
6 6
4 1
1 7
7 6
6 8
8 10
0


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

*/

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40