Submission #761229

#	Time	Username	Problem	Language	Result	Execution time	Memory
761229		penguin133	One-Way Streets (CEOI17_oneway)	C++17	30 / 100	55 ms	29092 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int low[200005], dep[200005];
vector <pi> adj[200005];
int brr[200005];
int n, m, q;
set <int> s[200005];
int L[200005], R[200005], S[200005], E[200005];
int huh[200005], cnt = 1;
 
void dfs(int x, int par, int d){
	dep[x] = low[x] = d;
	S[x] = cnt++;
	bool f = 0;
	vector <pi> tt;
	for(auto [i, j] : adj[x]){
		if(j == par)continue;
		if(dep[i]){
			low[x] = min(low[x], dep[i]);
		}
		else {
			dfs(i, j, d + 1);
			tt.push_back({i, j});
			
		}
	}
	for(auto [i, j] : tt){
		low[x] = min(low[x], low[i]);
		if(low[i] >= dep[i]){
			if(s[i].empty())continue;
			int tmp = *s[i].begin();
			if(S[i] <= S[L[tmp]] && E[L[tmp]] <= E[i])brr[j] = (huh[j] == i ? 1 : 2);
			else brr[j] = (huh[j] == i ? 2 : 1);
		}
		if(s[x].size() < s[i].size())swap(s[x], s[i]);
		for(auto k : s[i]){
			if(s[x].find(k) == s[x].end())s[x].insert(k);
			else s[x].erase(k);
		}
	}
	E[x] = cnt - 1;
}
 
void solve(){
	cin >> n >> m;
	for(int i=1;i<=m;i++){
		int a, b; cin >> a >> b;
		adj[a].push_back({b, i});
		adj[b].push_back({a, i});
		huh[i] = a;
	}
	cin >> q;
	for(int i=1;i<=q;i++){
		int a, b; cin >> a >> b;
		s[a].insert(i);
		s[b].insert(i);
		L[i] = a, R[i] = b;
	}
	for(int i=1;i<=n;i++)if(!dep[i])dfs(i, -1, 1);
	for(int i=1;i<=m;i++){
		if(!brr[i])cout << 'B';
		if(brr[i] == 1)cout << 'R';
		if(brr[i] == 2)cout << 'L';
	}
}
 
main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message (stderr)

oneway.cpp: In function 'void dfs(long long int, long long int, long long int)':
oneway.cpp:25:7: warning: unused variable 'f' [-Wunused-variable]
   25 |  bool f = 0;
      |       ^
oneway.cpp: At global scope:
oneway.cpp:78:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   78 | main(){
      | ^~~~

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