oj.uz

답안 #652771

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
652771 2022-10-24T09:18:37 Z alvingogo One-Way Streets (CEOI17_oneway) C++14
0 / 100
 1 ms 212 KB 
#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=1;
void dfs(int r,int f){
	dfn[r]=low[r]=cnt;
	cnt++;
	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[h.fs]){
				ans[h.sc]=1;
			}
		}
	}
}
void ftt(int r,int f){
	tt[r]=cc;
	for(auto h:e[r]){
		if(tt[h.fs]){
			continue;
		}
		if(ans[h.sc]==0){
			ftt(h.fs,h.sc);
		}
	}
	for(auto h:e[r]){
		if(tt[h.fs]){
			continue;
		}
		if(ans[h.sc]==1){
			cc++;
			ftt(h.fs,h.sc);
		}
	}
}
vector<int> kk;
vector<vector<pair<int,int> > > ff;
vector<int> deg;
vector<int> vis2;
void dfs3(int r,int f){
	if(kk[r]!=0 && deg[r]==1){
		vis2[r]=1;
		for(auto h:ff[r]){
			if(h.fs!=f){
				ans[h.sc]=1;
				deg[h.fs]--;
				dfs3(h.fs,r);
			}
		}
	}
}
vector<pair<int,int> > eg;
void dfs4(int r,int f){
	for(auto h:ff[r]){
		if(h.fs!=f){
			if(r!=0){
				if(eg[h.sc].sc==r){
					ans[h.sc]=-1;
				}
				else{
					ans[h.sc]=1;
				}
			}
			dfs4(h.fs,r);
		}
	}
}
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);
	for(int i=0;i<n;i++){
		if(!dfn[i]){
			dfs(i,-1);
		}
	}
	tt.resize(n);
	for(int i=0;i<n;i++){
		if(!tt[i]){
			ftt(i,-1);
		}
	}
	ff.resize(cc+1);
	deg.resize(cc+1);
	vis2.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});
				ff[tt[h.fs]].push_back({tt[i],h.sc});
				deg[tt[i]]++;
				deg[tt[h.fs]]++;
			}
		}
	}
	int p;
	cin >> p;
	kk.resize(n);
	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]=1;
		kk[b]=-1;
		ff[0].push_back({a,-1});
	}
	for(int i=1;i<=cc;i++){
		if(deg[i]==1){
			dfs3(i,i);
		}
	}
	dfs4(0,0);
	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
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -