oj.uz

Submission #761230

# Submission time Handle Problem Language Result Execution time Memory
761230 2023-06-19T11:26:54 Z penguin133 One-Way Streets (CEOI17_oneway) C++17
100 / 100
 313 ms 71416 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;
      if(a == b)continue;
		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: In function 'void solve()':
oneway.cpp:66:7: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   66 |       if(a == b)continue;
      |       ^~
oneway.cpp:67:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   67 |   s[a].insert(i);
      |   ^
oneway.cpp: At global scope:
oneway.cpp:79:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   79 | main(){
      | ^~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 7 ms 14548 KB Output is correct
4 Correct 8 ms 14548 KB Output is correct
5 Correct 9 ms 14548 KB Output is correct
6 Correct 7 ms 14576 KB Output is correct
7 Correct 8 ms 14568 KB Output is correct
8 Correct 7 ms 14592 KB Output is correct
9 Correct 8 ms 14588 KB Output is correct
10 Correct 7 ms 14548 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 7 ms 14548 KB Output is correct
4 Correct 8 ms 14548 KB Output is correct
5 Correct 9 ms 14548 KB Output is correct
6 Correct 7 ms 14576 KB Output is correct
7 Correct 8 ms 14568 KB Output is correct
8 Correct 7 ms 14592 KB Output is correct
9 Correct 8 ms 14588 KB Output is correct
10 Correct 7 ms 14548 KB Output is correct
11 Correct 45 ms 23280 KB Output is correct
12 Correct 46 ms 25000 KB Output is correct
13 Correct 47 ms 26860 KB Output is correct
14 Correct 58 ms 27980 KB Output is correct
15 Correct 77 ms 29252 KB Output is correct
16 Correct 58 ms 24852 KB Output is correct
17 Correct 63 ms 29004 KB Output is correct
18 Correct 62 ms 25296 KB Output is correct
19 Correct 73 ms 31432 KB Output is correct
20 Correct 44 ms 25320 KB Output is correct
21 Correct 39 ms 25556 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 7 ms 14548 KB Output is correct
4 Correct 8 ms 14548 KB Output is correct
5 Correct 9 ms 14548 KB Output is correct
6 Correct 7 ms 14576 KB Output is correct
7 Correct 8 ms 14568 KB Output is correct
8 Correct 7 ms 14592 KB Output is correct
9 Correct 8 ms 14588 KB Output is correct
10 Correct 7 ms 14548 KB Output is correct
11 Correct 45 ms 23280 KB Output is correct
12 Correct 46 ms 25000 KB Output is correct
13 Correct 47 ms 26860 KB Output is correct
14 Correct 58 ms 27980 KB Output is correct
15 Correct 77 ms 29252 KB Output is correct
16 Correct 58 ms 24852 KB Output is correct
17 Correct 63 ms 29004 KB Output is correct
18 Correct 62 ms 25296 KB Output is correct
19 Correct 73 ms 31432 KB Output is correct
20 Correct 44 ms 25320 KB Output is correct
21 Correct 39 ms 25556 KB Output is correct
22 Correct 247 ms 53532 KB Output is correct
23 Correct 291 ms 67148 KB Output is correct
24 Correct 313 ms 71416 KB Output is correct
25 Correct 210 ms 53784 KB Output is correct
26 Correct 237 ms 52352 KB Output is correct
27 Correct 261 ms 58720 KB Output is correct
28 Correct 122 ms 33000 KB Output is correct
29 Correct 231 ms 49132 KB Output is correct
30 Correct 200 ms 49408 KB Output is correct
31 Correct 197 ms 45984 KB Output is correct
32 Correct 184 ms 46992 KB Output is correct