Submission #1257113

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257113		nikaa123	One-Way Streets (CEOI17_oneway)	C++20	0 / 100	991 ms	327680 KiB

oneway

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

#define int long long
#define eb emplace_back
#define mp make_pair
#define pb push_back
#define pp pop_back
#define endl '\n'
#define ff first
#define ss second
#define stop exit(0)
#define sz(x) (int)x.size()
#define pause system("pause")
#define all(x) (x).begin(), (x).end()
#define deb(x) cout << #x << "-" << x << endl

typedef char chr;
typedef string str;
typedef long long ll;
typedef vector<int> vii;
typedef pair<int, int> pii;

const long long INF = LLONG_MAX;
const int inf = INT_MAX;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};
const double PI = 2 * acos(0.0);

const int N = 1e5 + 5;

int n,m,p,a,b;
vector <pii> roads;
int id;
vii lst;
int l;
int timer;

vector<vector<pii>> v, v1;
vector<int> visited, low, in, out, comp, parid;
vector<vector<int>> up;
vector<bool> isbridge;
vector<char> ans;

void dfs1(int x, int p) {
    visited[x] = true;
    in[x] = low[x] = timer++;
    for (auto [to,id]:v[x]) {
        if (to == p) continue;
        if (visited[to]) {
            low[x] = min(low[x],in[to]);
        } else {
            dfs1(to,x);
            low[x] = min(low[x],low[to]);
            if (low[to] > in[x]) {
                isbridge[id] = isbridge[id] = true;
                v1[x].pb({to,id});
                v1[to].pb({x,id});
            }
        }
    }
}

void dfs2(int x) {
    lst.pb(x);
    visited[x] = true;
    for (auto [to,id]:v[x]) {
        if (visited[to]) continue;
        if (isbridge[id]) continue;
        dfs2(to);
    }
}

void dfs3(int x, int p) {
    in[x] = timer++;
    up[x][0] = p;
    visited[x] = true;
    for (int i = 1; i <= 17; i++) {
        up[x][i] = up[up[x][i-1]][i-1];
    }
    for (auto [to,id]:v[x]) {
        if (to == p) continue;
        parid[to] = id;
        dfs3(to,x);
    }
    out[x] = timer++;
}

bool ispar(int a, int b) {
    return (in[a] < in[b] && out[a] > out[b]);
}

int lca(int a, int b) {
    if (ispar(a,b)) return a;
    if (ispar(b,a)) return b;
    for (int i = 17; i >= 0; i--) {
        if (!ispar(up[a][i],b)) {
            a = up[a][i];
        }
    }
    return up[a][0];
}

inline void test_case() {

    cin >> n >> m;
    v.assign(n*2, {});
    v1.assign(n*2, {});
    visited.assign(n*2, 0);
    low.assign(n*2, 0);
    in.assign(n*2, 0);
    out.assign(n*2, 0);
    comp.assign(n*2, 0);
    parid.assign(n*2, 0);
    up.assign(n*2, vector<int>(20, 0));
    isbridge.assign(m+m, false);
    ans.assign(m+m, 'B');

    roads.pb({0,0});
    for (int i = 1; i <= m; i++) {
        cin >> a >> b;
        v[a].pb({b,i});
        v[b].pb({a,i});
        roads.pb({a,b});
        ans[i] = 'B';
    }
    for (int i = 0; i <= n; i++) {
        low[i] = inf;
    }
    for (int i = 1; i <= n; i++) { 
        if (visited[i]) continue;
        dfs1(i,i);
    }
    for (int i = 1; i <= n; i++) {
        visited[i] = false;
    }
    id = n+1;
    for (int i = 1; i <= n; i++) {
        if (visited[i]) continue;
        lst.clear();
        dfs2(i);
        if (sz(lst) > 1) {
            for (auto x:lst) {
                comp[x] = id;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        visited[i] = false;
    }
    for (int i = 1; i <= m; i++) {
        auto [a,b] = roads[i];
        if (!isbridge[i]) {
            if (comp[a]) {
                v1[a].pb({comp[a],0});
                v1[comp[a]].pb({a,0});
            }
            if (comp[b]) {
                v1[b].pb({comp[b],0});
                v1[comp[b]].pb({b,0});
            }
        }
    }
    v = v1;
    for (int i = 1; i <= n; i++) {
        visited[i] = false;
    }
    for (int i = 1; i <= n; i++) {
        if (visited[i]) continue;
        dfs3(i,i);
        // deb(i);
    }
    // deb(parid[6]);
    cin >> p;
    while (p--) {
        cin >> a >> b;
        l = lca(a,b);
        // cout << "---> " << l << endl;
        while (a != l) {
            int x = up[a][0];
            // deb(x);
            pii r = {a,x};
            if (roads[parid[a]] == r) {
                ans[parid[a]] = 'R';
            } else {
                ans[parid[a]] = 'L';
            }
            a = x;

        }
        while (b != l) {
            int x = up[b][0];
            pii r = {x,b};
            if (roads[parid[b]] == r) {
                ans[parid[b]] = 'R';
            } else {
                ans[parid[b]] = 'L';
            }
            b = x;
        }
    }
    for (int i = 1; i <= m; i++) {
        cout << ans[i];
    }
    cout << endl;
    // for (auto [a,b]:roads) {
    //     cout << isbridge[{a,b}] << endl;
    // }
    // cout << endl;
    // for (auto [a,b]:newroads) {
    //     cout << a<< " " <<b << endl;
    // }


}

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

    int T = 1;
    // cin >> T;
    while (T--) {
        test_case();
    }
    return 0;
}

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