제출 #137995

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
137995		ckodser	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	7 ms	6136 KiB

oneway

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}

#define ll long long
#define pb push_back
#define ld long double
#define mp make_pair
#define F first
#define S second
#define pii pair<ll,ll> 

using namespace :: std;

const ll maxn=1e5+500;

vector<ll> tree[maxn];
ll s[maxn];
ll t[maxn];
ll d[maxn];
ll pare[maxn];
bool vis[maxn];

void dfs2(ll a,ll p=-1){
	vis[a]=1;
	for(auto e:tree[a]){
		ll v=(s[e]^t[e]^a);
		if(v!=p){
			dfs2(v,a);
			d[a]+=d[v];
		}else{
			pare[a]=e;
		}
	}
}

ll st[maxn];
ll et[maxn];
ll tt=0;

vector<ll> ger[maxn];
bool boreshi[maxn];
ll h[maxn];
ll dp[maxn];
ll par[maxn];
char ans[maxn];


ll findPar(ll a){
	if(par[a]==a)return a;
	par[a]=findPar(par[a]);
	return par[a];
}
void dfs(ll a,ll pe=-1){
	vis[a]=1;
	dp[a]=h[a];
	for(auto e:ger[a]){
		if(e!=pe){
			ll v=(a^s[e]^t[e]);
			if(!vis[v]){
				h[v]=h[a]+1;
				dfs(v,e);
				if(dp[v]==h[v]){
					boreshi[e]=1;
				}	
				dp[a]=min(dp[a],dp[v]);
			}else{
				dp[a]=min(dp[a],h[v]);
			}
		}
	}
}	
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);	
	ll n,m;
	cin>>n>>m;
	for(ll i=0;i<m;i++){
		cin>>s[i]>>t[i];
		s[i]--;t[i]--;
		ger[s[i]].pb(i);
		ger[t[i]].pb(i);
	}
	for(ll i=0;i<n;i++){
		if(vis[i]==0){
			dfs(0);
		}
	}
	for(ll i=0;i<n;i++){
		par[i]=i;
	}
	for(ll i=0;i<m;i++){
		if(!boreshi[i]){
			ll x=findPar(s[i]);
			ll y=findPar(t[i]);
			if(x!=y){
				par[x]=y;
			}
		}
	}
	for(ll i=0;i<m;i++){
		if(boreshi[i]){
			s[i]=findPar(s[i]);
			t[i]=findPar(t[i]);
			tree[s[i]].pb(i);
			tree[t[i]].pb(i);
		}
	}
	ll p;
	cin>>p;
	for(ll i=0;i<p;i++){
		ll x,y;
		cin>>x>>y;
		x--;y--;
		x=findPar(x);
		y=findPar(y);
		
		d[x]++;
		d[y]--;
	}

	memset(vis,0,sizeof vis);
	fill(pare,pare+maxn,-1);
	for(ll i=0;i<n;i++){
		if(par[i]==i && !vis[i]){
			dfs2(i);
		}
	}
	fill(ans,ans+maxn,'B');
	for(ll i=0;i<n;i++){
		if(par[i]==i){
			if(pare[i]>=0){
				if(d[i]!=0){
					ll e=pare[i];
					if(s[e]==i){
						ans[e]='R';
					}else{
						ans[e]='L';
					}
					if(d[i]<0){
						if(ans[e]=='L')ans[e]='R';
						else           ans[e]='L';
					}
				}
			}
		}
	}

	for(ll i=0;i<m;i++){
		cout<<ans[i];
	}
}

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