Submission #938235

#	Time	Username	Problem	Language	Result	Execution time	Memory
938235		vjudge1	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	0 ms	348 KiB

oneway

#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;
 
void solve(){	
	
	int n,m;
	cin >> n >> m;
	vector<vector<tuple<int,int,int>>> g(n + 1);
	for(int i = 0;i < m;i++){
		int a,b;
		cin >> a >> b;
		g[a].pb({b,1,i});
		g[b].pb({a,0,i});
	}
	string f = "";
	for(int i = 0;i < m;i++){
		f += 'B';
	}
	int p;
	cin >> p;
	string ans = f;
	int R[m + 1] {},L[m + 1] {};
	for(int i = 0;i < p;i++){
		int p1,p2;
		cin >> p1 >> p2;
		queue<int> q;
		q.push(p1);
		vector<tuple<int,int,int>> from(m + 1);
		vector<int> dis(n + 1,INF);
		dis[p1] = 0;
		from[p1] = {-1,-1,-1};
		while(!q.empty()){
			int top = q.front();
			q.pop();
			for(auto [to,type,ind] : g[top]){
				if(dis[top] + 1 < dis[to]){
					dis[to] = dis[top] + 1;
					from[to] = {top,type,ind};
					q.push(to);
				}
			}
		}
		string s = f;
		int now = p2;
		while(now != p1){
			auto[to,type,ind] = from[now];
			if(type == 0){
				s[ind] = 'L';
			} else{
				s[ind] = 'R';
			}
			now = to;
		}
		
		for(int j = 0;j < s.size();j++){
			if(s[j] == 'R'){
				R[j] = 1;
			} else if(s[j] == 'L'){
				L[j] = 1;
			}
		}
	}
	string res = "";
	for(int i = 0;i < m;i++){
		if(R[i] ^ L[i]){
			if(R[i]){
				res += 'R';
			} else{
				res += 'L';
			}
		} else{
			res += 'B';
		}
	}
	cout << res << "\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 (stderr)

oneway.cpp: In function 'void solve()':
oneway.cpp:71:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |   for(int j = 0;j < s.size();j++){
      |                 ~~^~~~~~~~~~

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