Submission #129970

#	Time	Username	Problem	Language	Result	Execution time	Memory
129970		TadijaSebez	One-Way Streets (CEOI17_oneway)	C++11	100 / 100	244 ms	29868 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=100050;
const int L=17;
vector<pair<int,int>> G[N];
vector<pair<int,int>> edges;
stack<int> s;
bool in[N];
int disc[N],low[N],tid;
int csz,comp[N];
void Tarjan(int u, int p)
{
	disc[u]=low[u]=++tid;
	s.push(u);in[u]=1;
	for(int i=0;i<G[u].size();i++) if(G[u][i].second!=p)
	{
		int v=G[u][i].first;
		if(!disc[v])
		{
			Tarjan(v,G[u][i].second);
			low[u]=min(low[u],low[v]);
		}
		else if(in[v]) low[u]=min(low[u],disc[v]);
	}
	if(disc[u]==low[u])
	{
		int v;
		csz++;
		do
		{
			v=s.top();
			s.pop();
			in[v]=0;
			comp[v]=csz;
		}while(v!=u);
	}
}
vector<pair<int,int>> E[N];
int up[N],par[N][L],dep[N];
int mnu[N],mnd[N];
void DFS(int u, int p)
{
	dep[u]=dep[p]+1;
	par[u][0]=p;
	for(int i=1;i<L;i++) par[u][i]=par[par[u][i-1]][i-1];
	mnu[u]=mnd[u]=1e9+7;
	for(auto e:E[u]) if(e.first!=p)
	{
		up[e.first]=e.second;
		DFS(e.first,u);
	}
}
int LCA(int u, int v)
{
	if(dep[u]<dep[v]) swap(u,v);
	for(int i=L-1;~i;i--) if(dep[par[u][i]]>=dep[v]) u=par[u][i];
	for(int i=L-1;~i;i--) if(par[u][i]!=par[v][i]) u=par[u][i],v=par[v][i];
	return u==v?v:par[v][0];
}
int ans[N];
void Solve(int u, int p)
{
	for(auto e:E[u]) if(e.first!=p)
	{
		int v=e.first;
		Solve(v,u);
		mnd[u]=min(mnd[u],mnd[v]);
		mnu[u]=min(mnu[u],mnu[v]);
	}
	if(mnu[u]<dep[u])
	{
		if(up[u]>0) ans[up[u]]=-1;
		else ans[-up[u]]=1;
	}
	if(mnd[u]<dep[u])
	{
		if(up[u]>0) ans[up[u]]=1;
		else ans[-up[u]]=-1;
	}
}
int main()
{
	int n,m,u,v;
	scanf("%i %i",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%i %i",&u,&v);
		G[u].pb({v,i});
		G[v].pb({u,i});
		edges.pb({u,v});
	}
	vector<int> root;
	for(int i=1;i<=n;i++) if(!disc[i]) Tarjan(i,0),root.pb(csz);
	for(int i=0;i<m;i++)
	{
		u=edges[i].first;
		v=edges[i].second;
		if(comp[u]!=comp[v])
		{
			E[comp[u]].pb({comp[v],i+1});
			E[comp[v]].pb({comp[u],-(i+1)});
		}
	}
	for(int r:root) DFS(r,0);
	int q;
	scanf("%i",&q);
	while(q--)
	{
		scanf("%i %i",&u,&v);
		u=comp[u];
		v=comp[v];
		int lca=LCA(u,v);
		mnu[u]=min(mnu[u],dep[lca]);
		mnd[v]=min(mnd[v],dep[lca]);
	}
	for(int r:root) Solve(r,0);
	for(int i=1;i<=m;i++)
	{
		if(ans[i]==0) printf("B");
		else if(ans[i]==1) printf("R");
		else printf("L");
	}
	return 0;
}

Compilation message (stderr)

oneway.cpp: In function 'void Tarjan(int, int)':
oneway.cpp:16:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<G[u].size();i++) if(G[u][i].second!=p)
              ~^~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:85:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
oneway.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i",&u,&v);
   ~~~~~^~~~~~~~~~~~~~~
oneway.cpp:107:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&q);
  ~~~~~^~~~~~~~~
oneway.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i",&u,&v);
   ~~~~~^~~~~~~~~~~~~~~

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