Submission #1226137

#TimeUsernameProblemLanguageResultExecution timeMemory
1226137giorgikobOne-Way Streets (CEOI17_oneway)C++20
100 / 100
127 ms43528 KiB
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6+5;

int n, m;
vector<pair<int,int>> gr[N];
int lvl[N], up[N], P[N][20];
int in[N], out[N];
int timer;
int A[N], B[N];

void dfs(int x, int ind, int p) {
    lvl[x] = lvl[p] + 1;

    P[x][0] = p;
    for (int i = 1; i < 20; i++) {
        P[x][i] = P[P[x][i-1]][i-1];
    }
    in[x] = timer++;

    for (auto [to, i] : gr[x]) {
        if (lvl[to] == 0) {
            dfs(to, i, x);
            up[x] += up[to];
        } else {
            if (i == ind) continue;
            if (lvl[to] < lvl[x]) {
                up[x]++;
            } else {
                up[x]--;
            }
        }
    }

    out[x] = timer;
}

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

int lca(int x, int y) {
    if (check(x, y)) return x;

    for (int i = 19; i >= 0; i--) {
        if (P[x][i] && !check(P[x][i], y)) {
            x = P[x][i];
        }
    }

    return P[x][0];
}

pair<int,int> edge[N];
int fix[N];
char answer[N];

void dfs1(int x, int ind) {
    fix[x] = 1;
    for (auto [to, i] : gr[x]) {
        if (fix[to]) continue;
        dfs1(to, i);
        A[x] += A[to];
        B[x] += B[to];
    }

    if (up[x] == 0 && ind != -1) {
        if (A[x] > 0) {
            if (edge[ind] == make_pair(x, P[x][0])) {
                answer[ind] = 'R';
            } else {
                answer[ind] = 'L';
            }
        } else if (B[x] > 0){
            if(edge[ind] == make_pair(x, P[x][0])) {
                answer[ind] = 'L';
            } else {
                answer[ind] = 'R';
            }
        }
    }
}


int main() {

    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        gr[x].push_back({y, i});
        gr[y].push_back({x, i});
        edge[i] = {x, y};
        answer[i] = 'B';
    }

    for (int i = 1; i <= n; i++) {
        if (lvl[i]) continue;
        dfs(i, -1, 0);
    }

    int k;
    cin >> k;
    while (k--) {
        int x, y;
        cin >> x >> y;
        int z = lca(x, y);
        A[x]++; A[z]--;
        B[y]++; B[z]--;
    }

    for (int i = 1; i <= n; i++) {
        if (fix[i]) continue;
        dfs1(i, -1);
    }

    for (int i = 0; i < m; i++) {
        cout << answer[i];
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...