oj.uz

Submission #938493

# Submission time Handle Problem Language Result Execution time Memory
938493 2024-03-05T07:59:46 Z vjudge1 One-Way Streets (CEOI17_oneway) C++17
30 / 100
 646 ms 604 KB 
#include "bits/stdc++.h"
 
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
 
using namespace __gnu_pbds; 
 
using namespace std;
 
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define ordered_mset tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 

const int INF = 1e18,N = 1001;
 
vector<vector<pair<int,int>>> g(N);

vector<int> vis(N);

void dfs(int n,int wow){
	vis[n] = 1;
	for(auto [v,ind] : g[n]){
		if(vis[v] != 1 && wow != ind){
			dfs(v,wow);
		}
	}
}

int checkRL(int u,int v,int a,int b,int ind){
	
	for(int j = 0;j < N;j++){
		vis[j] = 0;
	}
	
	dfs(u,ind);
	if(vis[a] == 1){
		return 1;
	} else if(vis[b] == 1){
		return 2;
	}
	for(int j = 0;j < N;j++){
		vis[j] = 0;
	}
	dfs(v,ind);
	if(vis[a] == 1){
		return 2;
	} else if(vis[b] == 1){
		return 1;
	}
	
} 

void solve(){	
	
	int n,m;
	cin >> n >> m;
	vector<pair<int,int>> rebro;
	for(int i = 0;i < m;i++){
		int a,b;
		cin >> a >> b;
		rebro.pb({a,b});
		g[a].pb({b,i});
		g[b].pb({a,i});
	}
	vector<pair<int,int>> vip;
	int p;
	cin >> p;
	for(int i = 0;i < p;i++){
		int a,b;
		cin >> a >> b;
		vip.pb({a,b});
	}
	int i = 0;
	vector<int> r(m + 1,1),l(m + 1,1);
	for(auto [u,v] : rebro){
		for(auto [fst,scn] : vip){
			for(int j = 0;j < N;j++){
				vis[j] = 0;
			}
			
			dfs(fst,i);
			if(vis[scn]){
				continue;
			}
			int type = checkRL(fst,scn,u,v,i);
			if(type == 1){
				r[i] = 1;
				l[i] = 0;
			}
			if(type == 2){
				l[i] = 1;
				r[i] = 0;
			}
		}
		i++;
	}
	string ans = "";
	for(int i = 0;i < m;i++){
		if(r[i] && l[i]){
			ans += 'B';
		} else if(r[i]){
			ans += 'R';
		} else{
			ans += 'L';
		}
	}
	cout << ans << "\n";
	
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	
	int t = 1;
//	cin >> t;
	while(t--){
		solve();
	}
}

Compilation message

oneway.cpp: In function 'long long int checkRL(long long int, long long int, long long int, long long int, long long int)':
oneway.cpp:55:1: warning: control reaches end of non-void function [-Wreturn-type]
   55 | }
      | ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 55 ms 348 KB Output is correct
4 Correct 26 ms 348 KB Output is correct
5 Correct 581 ms 572 KB Output is correct
6 Correct 377 ms 564 KB Output is correct
7 Correct 646 ms 580 KB Output is correct
8 Correct 532 ms 564 KB Output is correct
9 Correct 468 ms 560 KB Output is correct
10 Correct 352 ms 344 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 55 ms 348 KB Output is correct
4 Correct 26 ms 348 KB Output is correct
5 Correct 581 ms 572 KB Output is correct
6 Correct 377 ms 564 KB Output is correct
7 Correct 646 ms 580 KB Output is correct
8 Correct 532 ms 564 KB Output is correct
9 Correct 468 ms 560 KB Output is correct
10 Correct 352 ms 344 KB Output is correct
11 Runtime error 1 ms 604 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 55 ms 348 KB Output is correct
4 Correct 26 ms 348 KB Output is correct
5 Correct 581 ms 572 KB Output is correct
6 Correct 377 ms 564 KB Output is correct
7 Correct 646 ms 580 KB Output is correct
8 Correct 532 ms 564 KB Output is correct
9 Correct 468 ms 560 KB Output is correct
10 Correct 352 ms 344 KB Output is correct
11 Runtime error 1 ms 604 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -