제출 #1304885

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1304885		neonglitch	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	125 ms	31984 KiB

oneway

#include <iostream>
#include <vector>
#include <map>
using namespace std;
const int N=1e5+10,LG=18;
pair<int,int> edge[N];
int h[N],lw[N],par[N][LG],upe[N],up[N],su[N],eu[N],sd[N],ed[N],down[N];;
bool vis[N],bri[N];
vector<pair<int,int>> adj[N],ma[N];
void dfs(int x,int pid=0)
{
	vis[x]=1;
	for(int j=1;j<LG;j++)par[x][j]=par[par[x][j-1]][j-1];
	lw[x]=h[x];
	for(auto [y,id]:adj[x])
	{
		if(pid==id)continue;
		if(!vis[y])
		{
			// cout<<"adding "<<x<<' '<<y<<endl;
			ma[x].push_back({y,id});
			h[y]=h[x]+1;
			par[y][0]=x;
			dfs(y,id);
			if(lw[y]<h[y])
			{
				// cout<<"Non bridge "<<id<<endl;
				bri[id]=0;
			}
			lw[x]=min(lw[x],lw[y]);
		}
		else{
			// y is ancestor of x
			// cout<<"Edge "<<id<<' '<<x<<' '<<y<<endl;
			bri[id]=0;
			lw[x]=min(lw[x],h[y]);
		}
	}
	// cout<<"At "<<x<<' '<<h[x]<<' '<<lw[x]<<endl;
}
int lca(int x,int y)
{
	if(h[x]<h[y])swap(x,y);
	for(int j=LG-1;j>=0;j--)
	{
		if(h[par[x][j]]>=h[y])
		{
			x=par[x][j];
		}
	}
	if(x==y)return y;
	for(int j=LG-1;j>=0;j--)
	{
		if(par[x][j]!=par[y][j])
		{
			x=par[x][j];
			y=par[y][j];
		}
	}
	return par[x][0];
}
void dfs_(int x)
{
	up[x]+=su[x];
	down[x]+=sd[x];
	for(auto [y,id]:ma[x])
	{
		dfs_(y);
		up[y]-=eu[y];
		down[y]-=ed[y];
		if(up[y]>0)
		{
			upe[id]=y;
		}
		if(down[y]>0)
		{
			upe[id]=x;
		}
		up[x]+=up[y];
		down[x]+=down[y];
	}
	// cout<<"Hello "<<x<<' '<<up[x]<<' '<<down[x]<<endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin>>n>>m;
	for(int j=1;j<=m;j++)
	{
		int x,y;
		cin>>x>>y;
		edge[j]={x,y};
		adj[x].push_back({y,j});
		adj[y].push_back({x,j});
		bri[j]=(x!=y);
		upe[j]=-1;
	}
	// h[0]=0;
	vector<int> rt;
	for(int i=1;i<=n;i++)
	{
		if(!vis[i])h[i]=1,dfs(i),rt.push_back(i);
	}
	int p;
	cin>>p;
	for(int i=0;i<p;i++)
	{
		int x,y;
		cin>>x>>y;
		int l=lca(x,y);
		su[x]++;
		eu[l]++;
		sd[y]++;
		ed[l]++;
	}
	for(auto r:rt)
	{
		dfs_(r);
	}
	for(int j=1;j<=m;j++)
	{
		if(!bri[j] or upe[j]==-1)cout<<'B';
		else if(edge[j].first==upe[j])cout<<'R';
		else cout<<'L';
	}
	cout<<endl;
}

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