Submission #837938

#	Time	Username	Problem	Language	Result	Execution time	Memory
837938		jamielim	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	3 ms	5460 KiB

oneway

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,ii> i4;
typedef vector<int> vi;
const int MOD=1000000007;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const double PI=3.1415926536;
const double EPS=1e-14;

int n,m,p;
ii edge[100005];
vector<ii> adj[100005],adj2[100005];
bool bridge[100005];
char ans[100005];

int dep[100005],low[100005],ctr=1;
void dfs(int x,int pa){
	low[x]=dep[x]=ctr++;
	for(ii i:adj[x]){
		if(dep[i.fi]==0){
			dfs(i.fi,x);
			if(low[i.fi]>dep[x])bridge[abs(i.se)]=1;
			else low[x]=min(low[i.fi],low[x]);
		}else if(i.fi!=pa)low[x]=min(dep[i.fi],low[x]);
	}
}

int comp[100005],c=1;
void dfs2(int x){
	comp[x]=c;
	for(ii i:adj[x]){
		if(bridge[abs(i.se)])continue;
		if(comp[i.fi])continue;
		dfs2(i.fi);
	}
}

int par[20][100005];
ii dir[100005];
int idx[100005];
void dfs3(int x){
	for(ii i:adj2[x]){
		if(i.fi==par[0][x])continue;
		dep[i.fi]=dep[x]+1;
		par[0][i.fi]=x;
		idx[i.fi]=-i.se;
		dfs3(i.fi);
	}
}

int lca(int x,int y){
	if(dep[x]>dep[y])swap(x,y);
	for(int i=19;i>=0;i--)if(dep[par[i][y]]>=dep[x])y=par[i][y];
	if(x==y)return x;
	for(int i=19;i>=0;i--)if(par[i][x]!=par[i][y])x=par[i][x],y=par[i][y];
	return par[0][x];
}

ii dfs4(int x){
	ii cur=dir[x];
	for(ii i:adj2[x]){
		if(i.fi==par[0][x])continue;
		ii s=dfs4(i.fi);
		if(s.fi<=dep[x]){
			int j=abs(idx[i.fi])-1;
			if(s.se*idx[i.fi]>0)ans[j]='R';
			else if(s.se*idx[i.fi]<0)ans[j]='L';
		}
		cur=min(cur,s);
	}
	return cur;
}

int main(){
	scanf("%d%d",&n,&m);
	int a,b;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&a,&b);
		edge[i]=mp(a,b);
		adj[a].pb(b,i);
		adj[b].pb(a,-i);
	}
	for(int i=1;i<=n;i++){
		if(!dep[i]){
			dfs(i,0);
		}
	}
	for(int i=1;i<=n;i++){
		if(!comp[i]){
			dfs2(i);
			c++;
		}
	}
	for(int i=1;i<=m;i++){
		ans[i-1]='B';
		if(bridge[i]){
			a=comp[edge[i].fi],b=comp[edge[i].se];
			adj2[a].pb(b,i);
			adj2[b].pb(a,-i);
		}
	}
	memset(dep,0,sizeof(dep));
	for(int i=1;i<c;i++){
		if(!par[0][i]){
			dep[i]=1;
			dfs3(i);
		}
	}
	for(int i=1;i<20;i++)for(int j=1;j<c;j++)par[i][j]=par[i-1][par[i-1][j]];
	for(int i=1;i<c;i++)dir[i]=mp(INF,0);
	scanf("%d",&p);
	for(int i=0;i<p;i++){
		scanf("%d%d",&a,&b);
		a=comp[a];b=comp[b];
		if(a==b)continue;
		int l=lca(a,b);
		dir[a]=min(dir[a],mp(dep[l],1));
		dir[b]=min(dir[b],mp(dep[l],-1));
	}
	
	for(int i=1;i<c;i++){
		if(!par[0][i]){
			dfs4(i);
		}
	}
	printf("%s",ans);
}

Compilation message (stderr)

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]
   85 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
oneway.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |   scanf("%d%d",&a,&b);
      |   ~~~~~^~~~~~~~~~~~~~
oneway.cpp:121:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |  scanf("%d",&p);
      |  ~~~~~^~~~~~~~~
oneway.cpp:123:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |   scanf("%d%d",&a,&b);
      |   ~~~~~^~~~~~~~~~~~~~

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