oj.uz

Submission #761229

# Submission time Handle Problem Language Result Execution time Memory
761229 2023-06-19T11:21:46 Z penguin133 One-Way Streets (CEOI17_oneway) C++17
30 / 100
 55 ms 29092 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14436 KB Output is correct
3 Correct 8 ms 14592 KB Output is correct
4 Correct 8 ms 14496 KB Output is correct
5 Correct 7 ms 14548 KB Output is correct
6 Correct 8 ms 14536 KB Output is correct
7 Correct 8 ms 14548 KB Output is correct
8 Correct 10 ms 14596 KB Output is correct
9 Correct 7 ms 14548 KB Output is correct
10 Correct 8 ms 14572 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14436 KB Output is correct
3 Correct 8 ms 14592 KB Output is correct
4 Correct 8 ms 14496 KB Output is correct
5 Correct 7 ms 14548 KB Output is correct
6 Correct 8 ms 14536 KB Output is correct
7 Correct 8 ms 14548 KB Output is correct
8 Correct 10 ms 14596 KB Output is correct
9 Correct 7 ms 14548 KB Output is correct
10 Correct 8 ms 14572 KB Output is correct
11 Correct 38 ms 24400 KB Output is correct
12 Correct 40 ms 26148 KB Output is correct
13 Correct 46 ms 27972 KB Output is correct
14 Incorrect 55 ms 29092 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14436 KB Output is correct
3 Correct 8 ms 14592 KB Output is correct
4 Correct 8 ms 14496 KB Output is correct
5 Correct 7 ms 14548 KB Output is correct
6 Correct 8 ms 14536 KB Output is correct
7 Correct 8 ms 14548 KB Output is correct
8 Correct 10 ms 14596 KB Output is correct
9 Correct 7 ms 14548 KB Output is correct
10 Correct 8 ms 14572 KB Output is correct
11 Correct 38 ms 24400 KB Output is correct
12 Correct 40 ms 26148 KB Output is correct
13 Correct 46 ms 27972 KB Output is correct
14 Incorrect 55 ms 29092 KB Output isn't correct
15 Halted 0 ms 0 KB -