Submission #1246378

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246378		Thunnus	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	96 ms	31776 KiB

oneway

#include <bits/stdc++.h>
#define long long long
#define vi vector<int>
#define vvi vector<vi>

using namespace std;

const int N = (int) 1E5;

int t[N], c;
vector<int> a[N];

/*
namespace BCC {
	int n, timer = 0;
    vi tin(N, -1), low(N);
    stack<int> s;
    vvi adj(N);

    inline void add(int a, int b){
        adj[a].emplace_back(b);
        adj[b].emplace_back(a);
        return;
    }

    inline void dfs(int v, int p){
        tin[v] = low[v] = ++timer;
        for(int &u : adj[v]){
            if(u == p) continue;
            if(tin[u] != -1){
                low[v] = min(low[v], tin[u]);
            }
            else{
                dfs(u, v);
                low[v] = min(low[v], low[u]);
            }
        }
        if(low[v] == tin[v]){
            while(s.top() != v){
                t[s.top()] = c;
                a[c].emplace_back(s.top());
                s.pop();
            }
            t[s.top()] = c;
            a[c++].emplace_back(s.top());
            s.pop();
        }
        return;
    }

    inline void solve(int p){
        n = p;
        for(int i = 0; i < n; i++){
            if(tin[i] == -1){
                dfs(i, i);
            }
        }
        return;
    }
};
*/

	namespace BCC {
	int n;
	int d[N], f[N], x;
	vector<int> e[N];
	stack<int> s;
	
	void add(int u, int v) {
		e[u].push_back(v);
		e[v].push_back(u);
	}
	
	void DFS(int u, int p = 0 - 1) {
		d[u] = x;
		x = x + 1;
		f[u] = d[u];
		s.push(u);
		
		int o = 0;
		for (auto v : e[u]) {
			if (v == p && o == 0) {
				o = 1;
				continue;
			}
			if (d[v] < 0) {
				DFS(v, u);
				f[u] = min(f[u], f[v]);
			} else {
				f[u] = min(f[u], d[v]);
			}
		}
		
		if (f[u] == d[u]) {
			while (s.top() != u) {
				t[s.top()] = c;
				a[c].push_back(s.top());
				s.pop();
			}
			t[s.top()] = c;
			a[c].push_back(s.top());
			s.pop();
			c = c + 1;
		}
	}
	
	void solve(int p) {
		n = p;
		fill(d, d + n, 0 - 1);
		for (int u = 0; u < n; u++) {
			if (d[u] < 0) {
				DFS(u);
			}
		}
	}
};

int n, m;
vector<array<int, 3>> e[N];

int k;
char s[N];
int p[N], d[N];
vector<array<int, 3>> E[N];

void DFS(int u) {
	for (auto A : E[u]) {
		int v = A[0], i = A[1], x = A[2];
		if (v != p[u]) {
			p[v] = u;
			DFS(v);
			if (d[v] > 0) {
				s[i] = (x > 0 ? 'R' : 'L');
			} 
			if (d[v] < 0) {
				s[i] = (x > 0 ? 'L' : 'R');
			}
			d[u] = d[u] + d[v];
		}
	}
	if (p[u] < 0) {
		assert(d[u] == 0);
	}
}

void solve() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		u = u - 1, v = v - 1;
		e[u].push_back({v, i, 0});
		e[v].push_back({u, i, 1});
		BCC::add(u, v);
	}
	BCC::solve(n);
	
	for (int u = 0; u < n; u++) {
		for (auto A : e[u]) {
			int v = A[0], i = A[1], x = A[2];
			if (t[u] != t[v] && x == 0) {
				E[t[u]].push_back({t[v], i, 0});
				E[t[v]].push_back({t[u], i, 1});
			}
		}
	}
	
	cin >> k;
	for (int i = 0; i < k; i++) {
		int u, v;
		cin >> u >> v;
		u = u - 1, v = v - 1;
		d[t[u]] = d[t[u]] + 1;
		d[t[v]] = d[t[v]] - 1;
	}
	
	fill(s, s + m, 'B');
	fill(p, p + c, 0 - 1);
	for (int u = 0; u < c; u++) {
		if (p[u] < 0) {
			DFS(u);
		}
	}
	
	for (int i = 0; i < m; i++) {
		cout << s[i];
	}
	cout << "\n";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	int t;
	t = 1;
	for (int i = 0; i < t; i++) {
		solve();
	}
	return 0;
}

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