Submission #462605

#	Time	Username	Problem	Language	Result	Execution time	Memory
462605		JovanB	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	268 ms	35208 KiB

oneway

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int cnt;

int in[100005];
int low[100005];
bool visited[100005];
vector <int> graf[100005];
vector <int> dgraf[100005];
vector <int> tree[100005];
int a[100005];
int b[100005];
int qa[100005];
int qb[100005];

void dfs1(int v, int prnt){
    low[v] = in[v] = ++cnt;
    visited[v] = 1;
    for(auto c : graf[v]){
        if(c == prnt) continue;
        if(visited[c]){
            dgraf[v].push_back(c);
            dgraf[c].push_back(v);
            low[v] = min(low[v], in[c]);
            continue;
        }
        dfs1(c, v);
        low[v] = min(low[v], low[c]);
    }
    if(!prnt) return;
    if(low[v] <= in[prnt]){
        dgraf[v].push_back(prnt);
        dgraf[prnt].push_back(v);
    }
}

int ncomp;
int comp[100005];

void dfs2(int v){
    comp[v] = ncomp;
    //cout << v << " je u " << ncomp << endl;
    for(auto c : dgraf[v]){
        if(!comp[c]) dfs2(c);
    }
}

int out[100005];
int par[100005][22];
int gore[100005];
int depth[100005];

void dfs3(int v, int prnt){
    visited[v] = 1;
    par[v][0] = prnt;
    in[v] = ++cnt;
    for(int j=1; j<18; j++){
        par[v][j] = par[par[v][j-1]][j-1];
    }
    for(auto c : tree[v]){
        //if(visited[c]) continue;
        if(c == prnt) continue;
        depth[c] = depth[v] + 1;
        dfs3(c, v);
    }
    out[v] = ++cnt;
}

bool is_parent(int x, int y){
    return in[x] <= in[y] && out[y] <= out[x];
}

int lca(int x, int y){
    if(is_parent(x, y)) return x;
    if(is_parent(y, x)) return y;
    for(int j=17; j>=0; j--){
        if(!par[x][j]) continue;
        if(!is_parent(par[x][j], y)) x = par[x][j];
    }
    return par[x][0];
}

bool cmp(pair <int, int> a, pair <int, int> b){
    return depth[a.second] < depth[b.second];
}

int main() {
    ios_base::sync_with_stdio(false);
    cout.precision(10);
    cout << fixed;
    
    int n, m, q;
    cin >> n >> m;
    for(int i=1; i<=m; i++){
        cin >> a[i] >> b[i];
        graf[a[i]].push_back(b[i]);
        graf[b[i]].push_back(a[i]);
    }
    cin >> q;
    for(int i=1; i<=q; i++){
        cin >> qa[i] >> qb[i];
    }
    for(int i=1; i<=n; i++){
        if(!visited[i]) dfs1(i, 0);
    }
    for(int i=1; i<=n; i++){
        if(!comp[i]){
            ncomp++;
            dfs2(i);
        }
    }
    for(int i=1; i<=m; i++){
        if(comp[a[i]] == comp[b[i]]) continue;
        tree[comp[a[i]]].push_back(comp[b[i]]);
        tree[comp[b[i]]].push_back(comp[a[i]]);
        //cout << comp[a[i]] << " " << comp[b[i]] << "\n";
    }
    cnt = 0;
    for(int i=1; i<=ncomp; i++) visited[i] = 0;
    for(int i=1; i<=ncomp; i++){
        if(!visited[i]){
            dfs3(i, 0);
        }
    }
    vector <pair <int, int>> queries;
    for(int i=1; i<=q; i++){
        int k = lca(comp[qa[i]], comp[qb[i]]);
        queries.push_back({comp[qa[i]], k});
    }
    sort(queries.begin(), queries.end(), cmp);
    for(auto c : queries){
        int x = c.first;
        while(x != c.second){
            if(gore[x]) break;
            gore[x] = -1;
            x = par[x][0];
        }
    }
    queries.clear();
    for(int i=1; i<=q; i++){
        int k = lca(comp[qa[i]], comp[qb[i]]);
        queries.push_back({comp[qb[i]], k});
    }
    sort(queries.begin(), queries.end(), cmp);
    for(auto c : queries){
        int x = c.first;
        while(x != c.second){
            if(gore[x]) break;
            gore[x] = 1;
            x = par[x][0];
        }
    }
    for(int i=1; i<=m; i++){
        if(comp[a[i]] == comp[b[i]]){
            cout << "B";
            continue;
        }
        if((gore[comp[a[i]]] == 1 && par[comp[a[i]]][0] == comp[b[i]]) || (gore[comp[b[i]]] == -1 && par[comp[b[i]]][0] == comp[a[i]])) cout << "L";
        else if((gore[comp[a[i]]] == -1 && par[comp[a[i]]][0] == comp[b[i]]) || (gore[comp[b[i]]] == 1 && par[comp[b[i]]][0] == comp[a[i]])) cout << "R";
        else cout << "B";
    }
    return 0;
}

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