Submission #1221246

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221246		boclobanchat	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	99 ms	31120 KiB

oneway

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
map< pair<int,int>,int > mp;
vector< pair<int,int> > ds[MAXN],dst[MAXN];
vector<int> sd[MAXN],stp;
int low[MAXN],num[MAXN],ans[MAXN],col[MAXN],root[MAXN],idx[MAXN],pref[MAXN],tdfs=0,cc=0;
pair<int,int> edge[MAXN];
bool ck[MAXN];
void dfs(int i,int pre)
{
	low[i]=num[i]=++tdfs;
	for(auto v:ds[i])
	{
		if(v.first==pre) continue;
		if(!num[v.first])
		{
			dfs(v.first,i);
			low[i]=min(low[i],low[v.first]);
			if(low[v.first]==num[v.first]);
			else sd[i].push_back(v.first),sd[v.first].push_back(i),ans[v.second]=-1;
		}
		else low[i]=min(low[i],num[v.first]),sd[i].push_back(v.first),sd[v.first].push_back(i),ans[v.second]=-1;
	}
}
void dfs2(int i)
{
	col[i]=cc;
	for(auto v:sd[i]) if(!col[v]) dfs2(v);
}
void dfs3(int i,int pre)
{
	ck[i]=true;
	for(auto v:dst[i]) if(!ck[v.first])
	{
		idx[v.first]=v.second,root[v.first]=i;
		dfs3(v.first,i);
	}
}
void dfs4(int i,int pre)
{
	for(auto v:dst[i]) if(v.first!=pre)
	{
		dfs4(v.first,i);
		pref[i]+=pref[v.first];
	}
	if(i!=pre)
	{
		if(pref[i]<0)
		{
			if(col[edge[idx[i]].second]==i) ans[idx[i]]=0;
			else ans[idx[i]]=1;
		}
		if(pref[i]>0)
		{
			if(col[edge[idx[i]].second]==i) ans[idx[i]]=1;
			else ans[idx[i]]=0;
		}
		if(pref[i]==0) ans[idx[i]]=-1;
	}
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m,q;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
    	int l,r;
    	cin>>l>>r;
    	edge[i]={l,r};
    	if(l>r) swap(l,r);
    	ds[l].push_back({r,i}),ds[r].push_back({l,i});
    	if(mp[{l,r}]) ans[i]=ans[mp[{l,r}]]=-1;
		mp[{l,r}]=i;
	}
	for(int i=1;i<=n;i++) if(!num[i]) dfs(i,i);
	for(int i=1;i<=n;i++) if(!col[i])
	{
		cc++;
		dfs2(i);
	}
	for(int i=1;i<=m;i++) if(col[edge[i].first]!=col[edge[i].second])
	{
		dst[col[edge[i].first]].push_back({col[edge[i].second],i});
		dst[col[edge[i].second]].push_back({col[edge[i].first],i});
	}
	for(int i=1;i<=cc;i++) if(!ck[i])
	{
		dfs3(i,i);
		stp.push_back(i);
	}
	cin>>q;
	while(q--)
	{
		int x,y;
		cin>>x>>y;
		pref[x=col[x]]++,pref[y=col[y]]--;
	}
	for(auto v:stp) dfs4(v,v);
	for(int i=1;i<=m;i++) if(ans[i]==-1) cout<<"B";
	else if(ans[i]==1) cout<<"L";
	else cout<<"R";
}

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