제출 #237403

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

oneway

#include<bits/stdc++.h>
using namespace std;
int n,m,k,u,v,mn[100005],ind[100005],fix[100005],bridge[100005],F[100005],sum[100005],timer,tmin[100005],q;
char ans[100005];
vector<pair<int,pair<int,int> > >V[100005],B[100005];
map<int,int>FX[100005];
void dfs(int u,int p) {
	fix[u]=1;
	timer++;
	tmin[u]=mn[u]=timer;
	for(int i=0; i<V[u].size(); i++) {
		int v=V[u][i].first;
		if(v==p) continue;
		if(fix[v]==0) {
			dfs(v,u);
			mn[u]=min(mn[u],mn[v]);
			if(mn[v]>tmin[u] && FX[v][u]==1) {
				bridge[V[u][i].second.first]=1;
				F[v]=1;
				F[u]=1;

			}
		} else mn[u]=min(mn[u],tmin[v]);

	}
//	cout<<u<<"++"<<mn[u]<<endl;

}
void dfs1(int u,int p,int nm) {
	if(nm==1)fix[u]=2;
	else fix[u]=4;
	if(nm==1)ind[u]=p;
	for(int i=0; i<V[u].size(); i++) {
		int c=0;
		if(nm==2) c=4;
		else c=2;
		if(nm==2)if(bridge[V[u][i].second.first]!=0 &&fix[V[u][i].first]!=c ) {
				int v=V[u][i].first;
				B[ind[v]].push_back({p,{V[u][i].second.first,V[u][i].second.second}});
				B[p].push_back({ind[v],{V[u][i].second.first,1-V[u][i].second.second}});
			}
		if(fix[V[u][i].first]!=c && bridge[V[u][i].second.first]==0) {
			dfs1(V[u][i].first,p,nm);
		}

	}
}
void dfs2(int u,int p) {
	fix[u]=3;
	for(int i=0; i<B[u].size(); i++) {

		int v=B[u][i].first;
		if(v!=p ) {
			dfs2(v,u);
			sum[u]+=sum[v];

			if(sum[v]>0) {
				if(B[u][i].second.second==1) {
					ans[B[u][i].second.first]='R';
				} else ans[B[u][i].second.first]='L';
			}
			if(sum[v]<0) {
				if(B[u][i].second.second==1) {
					ans[B[u][i].second.first]='L';
				} else ans[B[u][i].second.first]='R';

			}
		}
	}
}
int main() {
	cin>>n>>m;
	
	for(k=1; k<=m; k++) {
		cin>>u>>v; FX[u][v]++;
		FX[v][u]++;
		V[u].push_back({v,{k,1}});
		V[v].push_back({u,{k,0}});
		ans[k]='B';
	}

	for(k=1; k<=n; k++)
		if(!fix[k])
			dfs(k,0);


	for(k=1; k<=n; k++) {
		if(F[k] && fix[k]!=2)dfs1(k,k,1);
	}
	for(k=1; k<=n; k++) {
		if(F[k] && fix[k]!=4)dfs1(k,k,2);
	}
	cin>>q;
	while(q--) {
		cin>>u>>v;
		sum[ind[u]]++;
		sum[ind[v]]--;
	}

	for(k=1; k<=n; k++) {
		if(fix[ind[k]]!=3 ) {
			dfs2(ind[k],0);
		}
	}
	for(k=1; k<=m; k++) {
		cout<<ans[k];
	}
}

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

oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:11:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<V[u].size(); i++) {
               ~^~~~~~~~~~~~
oneway.cpp: In function 'void dfs1(int, int, int)':
oneway.cpp:33:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<V[u].size(); i++) {
               ~^~~~~~~~~~~~
oneway.cpp: In function 'void dfs2(int, int)':
oneway.cpp:50:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<B[u].size(); i++) {
               ~^~~~~~~~~~~~

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