oj.uz

답안 #938394

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
938394 2024-03-05T05:43:11 Z vjudge1 One-Way Streets (CEOI17_oneway) C++17
0 / 100
 3 ms 15192 KB 
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pb push_back
#define fr first
#define sc second
const long long INF=1e17,N=2e5+6;
vector<int> ar[N],up(N),tin(N),color(N);
vector<bool> used(N);
int timer,mxcol=0;
map<pair<int,int>,bool> mp;
map<pair<int,int>,int> e_cnt;
void bridge(int x, int p=-1){
	used[x]=1;
	tin[x]=up[x]=timer++;
	for(auto it: ar[x]){
		if(it==p) continue;
		if(used[it])
			up[x]=min(up[x],tin[it]);
		else{
			bridge(it,x);
			up[x]=min(up[x],up[it]);
			if(up[it]>tin[x]){
				mp[{it,x}]=1;
				mp[{x,it}]=1;
			}
		}
	}
}
void dfs(int x, int c){
	color[x]=c;
	used[x]=1;
	for(auto it: ar[x]){
		if(!used[it] && (!mp[{x,it}] || e_cnt[{x,it}]!=1))
			dfs(it,c);
	}
}

int n,m;
int ans[N],A[N],B[N];
map<pair<int,int>,int> edge;
vector<pair<int,int>> g[N];
int k;
int vis[N];
void DFS(int x){
	vis[x]=1;
	for(auto it: g[x]){
		if(vis[it.fr]) continue;
		DFS(it.fr);
		A[x]+=A[it.fr];
		B[x]+=B[it.fr];
	}
	for(auto it: g[x]){
		if(vis[it.fr]) continue;
		if(A[it.fr]!=B[it.fr]){
			int t=it.sc;
			if(t<0)
				ans[-t]=1;
			else
				ans[t]=0;
			if(B[it.fr]>A[it.fr]) ans[abs(t)]^=1;
		}
	}
	vis[x]=0;
}
int c=0;
void get(){
	cin>>k;
	for(int i=0;i<k;i++){
		int a,b;cin>>a>>b;a--,b--;
		A[color[a]]++,B[color[b]]++;
		//DFS(color[a],color[b]);
	}
	DFS(1);
	for(int i=1;i<=m;i++){
		if(ans[i]==2) cout<<'B';
		else if(ans[i]==1) cout<<'R';
		else cout<<'L';
	}
}
void solve(){
	cin>>n>>m;
	vector<pair<int,int>> e;
	for(int i=0;i<m;i++){
		ans[i+1]=2;
		int a,b;
		cin>>a>>b;
		a--;
		b--;
		e_cnt[{a,b}]++;
		e_cnt[{b,a}]++;
		ar[a].pb(b);
		ar[b].pb(a);
		edge[{a,b}]=i+1;
		edge[{b,a}]=-i-1;
		e.pb({a,b});
	}
	for(int i=0;i<n;i++){
		if(!used[i])
			bridge(i);
	}
	used.assign(N,0);
	
	for(int i=0;i<n;i++){
		if(!used[i])
			dfs(i,++c);
	}	
	for(auto it: e){
		if(color[it.fr]!=color[it.sc]){
			g[color[it.fr]].pb({color[it.sc],edge[it]});
			g[color[it.sc]].pb({color[it.fr],edge[{it.sc,it.fr}]});
		}
	}
	get();
}
main(){
	int T=1;
	//cin>>T;
	while(T--){
		solve();
	}
}

Compilation message

oneway.cpp:116:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  116 | main(){
      | ^~~~

Subtask #1
0 / 30.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 40.0

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