제출 #246944

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
246944		errorgorn	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	392 ms	55312 KiB

oneway

//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a,Args... args){return max(a,MAX(args...));}
template<typename... Args>
ll MIN(ll a,Args... args){return min(a,MIN(args...));}

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n,m,q;
vector<ii> al[100005];

int dfs_time[100005];
int low[100005];

set<int> s[100005];
int ans[100005];

int TIME=1;

void dfs(int i,int p){
	dfs_time[i]=low[i]=TIME++;

	for (auto &it:al[i]){
		if (it.se==~p) continue;
		
		if (!dfs_time[it.fi]){
			dfs(it.fi,it.se);
			low[i]=min(low[i],low[it.fi]);
			
			//merge sets
			if (sz(s[it.fi])>sz(s[i])) swap(s[it.fi],s[i]);
			
			for (auto &val:s[it.fi]){
				if (s[i].count(~val)) s[i].erase(~val);
				else s[i].insert(val);
			}
		}
		else{
			low[i]=min(low[i],dfs_time[it.fi]);
		}
	}
	
	int rp=(p>=0?p:~p);
	if (low[i]==dfs_time[i] && !s[i].empty()){
		if (((*s[i].begin())>=0)==(p>=0)) ans[rp]=1;
		else ans[rp]=2;
	}
}



int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>m;
	
	int a,b;
	rep(x,0,m){
		cin>>a>>b;
		
		al[a].push_back(ii(b,x));
		al[b].push_back(ii(a,~x));
	}
	
	cin>>q;
	rep(x,0,q){
		cin>>a>>b;
		
		if (a==b) continue; //think
		
		s[a].insert(x);
		s[b].insert(~x);
	}
	
	rep(x,1,n+1) if (!dfs_time[x]){
		dfs(x,1e9);
	}
	
	rep(x,0,m){
		if (ans[x]==1) cout<<"L";
		else if (ans[x]==2) cout<<"R";
		else cout<<"B";
	}
}

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