Submission #760350

#	Time	Username	Problem	Language	Result	Execution time	Memory
760350		MohamedFaresNebili	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	83 ms	17036 KiB

oneway

#include <bits/stdc++.h>

            using namespace std;

            int N, M, Q, X[100005], Y[100005], P[100005];
            int timer, E[100005], tin[100005], low[100005];
            int S[100005], dep[100005];
            bool isBridge[100005];
            vector<int> adj[100005];

            int findSet(int v) {
                if(P[v] == v) return v;
                return P[v] = findSet(P[v]);
            }
            void unionSet(int u, int v) {
                u = findSet(u), v = findSet(v);
                if(u == v) return;
                P[u] = v;
            }
            void dfs(int v, int p) {
                tin[v] = low[v] = timer++;
                for(auto e : adj[v]) {
                    int u = v ^ E[e];
                    if(tin[u] != -1 && e != p) low[v] = min(low[v], tin[u]);
                    else if(tin[u] == -1) {
                        dfs(u, e);
                        low[v] = min(low[v], low[u]);
                        if(low[u] > tin[v]) isBridge[e] = 1;
                    }
                }
            }
            void solve(int v, int p) {
                for(auto e : adj[v]) {
                    int u = v ^ E[e];
                    if(u == p) continue;
                    dep[u] = dep[v] + 1;
                    solve(u, v); S[v] += S[u];
                }
            }

            int32_t main() {
                ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
                cin >> N >> M;
                for(int l = 1; l <= N; l++) P[l] = l;
                for(int l = 1; l <= M; l++) {
                    cin >> X[l] >> Y[l];
                    E[l] = X[l] ^ Y[l];
                    adj[X[l]].push_back(l);
                    adj[Y[l]].push_back(l);
                }
                memset(tin, -1, sizeof tin);
                for(int l = 1; l <= N; l++)
                    if(tin[l] == -1) dfs(l, -1);
                for(int l = 1; l <= M; l++) {
                    if(!isBridge[l]) unionSet(X[l], Y[l]);
                }
                for(int l = 1; l <= N; l++) adj[l].clear();
                for(int l = 1; l <= M; l++) {
                    if(!isBridge[l]) continue;
                    X[l] = findSet(X[l]);
                    Y[l] = findSet(Y[l]);
                    E[l] = X[l] ^ Y[l];
                    adj[X[l]].push_back(l);
                    adj[Y[l]].push_back(l);
                }
                cin >> Q;
                while(Q--) {
                    int U, V; cin >> U >> V;
                    U = findSet(U), V = findSet(V);
                    S[U]++, S[V]--;
                }
                for(int l = 1; l <= N; l++) {
                    if(P[l] == l && !dep[l]) {
                        dep[l] = 1; solve(l, l);
                    }
                }
                for(int l = 1; l <= M; l++) {
                    if(!isBridge[l]) { cout << 'B'; continue; }
                    int U = X[l], V = Y[l];
                    if(dep[U] < dep[V]) swap(U, V);
                    if(S[U]) cout << (((S[U] > 0) == (U == X[l])) ? 'R' : 'L');
                    else cout << 'B';
                }
                return 0;
            }

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