제출 #938396

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
938396		vjudge1	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	534 ms	69064 KiB

oneway

#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, int p){
	vis[x]=1;
	for(auto it: g[x]){
		if(it.fr==p) continue;
		DFS(it.fr,x);
		A[x]+=A[it.fr];
		B[x]+=B[it.fr];
	}
	for(auto it: g[x]){
		if(it.fr==p) 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;
		}
	}
}
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]);
	}
	for(int i=1;i<=c;i++)
		if(!vis[i])
			DFS(i,-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();
	}
}

컴파일 시 표준 에러 (stderr) 메시지

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

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