제출 #652772

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

oneway

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define cd complex<double>
#define p_q priority_queue
using namespace std;

vector<vector<pair<int,int> > > e;
vector<int> dfn,low;
vector<int> ans;
vector<int> vis;
vector<int> tt;
int cnt=1,cc=0;
stack<int> sk;
void dfs(int r,int f){
	dfn[r]=low[r]=cnt;
	cnt++;
	sk.push(r);
	if(f>=0){
		vis[f]=1;
	}
	for(auto h:e[r]){
		if(vis[h.sc]){
			continue;
		}
		if(dfn[h.fs]){
			low[r]=min(low[r],dfn[h.fs]);
		}
		else{
			dfs(h.fs,h.sc);
			low[r]=min(low[r],low[h.fs]);
			if(low[h.fs]>dfn[r]){
				cc++;
				int k;
				do{
					k=sk.top();
					tt[k]=cc;
					sk.pop();
				}while(k!=h.fs);
			}
		}
	}
	if(f==-1){
		cc++;
		do{
			tt[sk.top()]=cc;
			sk.pop();
		}while(sk.size());
	}
}
vector<vector<pair<int,int> > > ff;
vector<pair<int,int> > eg;
vector<int> kk;
vector<int> vvvvv;
void dfs2(int x,int y,int z){
	vvvvv[x]=1;
	for(auto h:ff[x]){
		if(h.fs!=y){
			dfs2(h.fs,x,h.sc);
			kk[x]+=kk[h.fs];
		}
	}
	if(kk[x]!=0){
		ans[z]=((kk[x]>0)^(x==eg[z].fs))?1:-1;
	}
}
int main(){
	AquA;
	int n,m;
	cin >> n >> m;
	e.resize(n);
	eg.resize(m);
	for(int i=0;i<m;i++){
		int a,b;
		cin >> a >> b;
		a--;
		b--;
		e[a].push_back({b,i});
		e[b].push_back({a,i});
		eg[i]={a,b};
	}
	dfn.resize(n);
	low.resize(n);
	ans.resize(m);
	vis.resize(m);
	tt.resize(n);
	for(int i=0;i<n;i++){
		if(!dfn[i]){
			dfs(i,-1);
		}
	}
	ff.resize(cc+1);
	for(int i=0;i<n;i++){
		for(auto h:e[i]){
			if(tt[i]!=tt[h.fs]){
				ff[tt[i]].push_back({tt[h.fs],h.sc});
			}
		}
	}
	for(int i=0;i<m;i++){
		eg[i]={tt[eg[i].fs],tt[eg[i].sc]};
	}
	int p;
	cin >> p;
	kk.resize(cc+1);
	for(int i=0;i<p;i++){
		int a,b;
		cin >> a >> b;
		a--;
		b--;
		a=tt[a];
		b=tt[b];
		if(a==b){
			continue;
		}
		kk[a]++;
		kk[b]--;
	}
	/*
	for(int i=0;i<=cc;i++){
		cout << i << "\n";
		for(auto h:ff[i]){
			cout << h.fs << " " << h.sc << "\n";
		}
		cout << "\n";
	}
	*/	
	vvvvv.resize(cc+1);
	for(int i=1;i<=cc;i++){
		if(vvvvv[i]==0){
			dfs2(i,0,-1);
		}
	}
	for(int i=0;i<m;i++){
		if(ans[i]==0){
			cout << "B";
		}
		else if(ans[i]==1){
			cout << "L";
		}
		else if(ans[i]==-1){
			cout << "R";
		}
	}
	return 0;
}

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