Submission #837957

#	Time	Username	Problem	Language	Result	Execution time	Memory
837957		jamielim	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	226 ms	35684 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];
int dir[20][100005];
int idx[100005];
void dfs3(int x){
	for(ii i:adj2[x]){
		if(i.fi==par[0][x]||i.fi==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];
}
 
void direct(int x,int y,int d){
	if(x==y)return;
	for(int i=19;i>=0;i--){
		if(dep[par[i][x]]>=dep[y]){
			dir[i][x]=d;
			x=par[i][x];
		}
	}
}
 
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]];
	
	scanf("%d",&p);
	for(int i=0;i<p;i++){
		scanf("%d%d",&a,&b);
		if(comp[a]==comp[b])continue;
		int l=lca(comp[a],comp[b]);
		direct(comp[a],l,1);
		direct(comp[b],l,-1);
	}
	
	for(int i=19;i>0;i--){
		for(int j=1;j<c;j++){
			if(dir[i][j]!=0){
				dir[i-1][j]=dir[i][j];
				dir[i-1][par[i-1][j]]=dir[i][j];
			}
		}
	}
	for(int i=1;i<c;i++){
		if(idx[i]==0)continue;
		if(dir[0][i]*idx[i]>0)ans[abs(idx[i])-1]='R';
		else if(dir[0][i]*idx[i]<0)ans[abs(idx[i])-1]='L';
	}
	printf("%s",ans);
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
oneway.cpp:83:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |   scanf("%d%d",&a,&b);
      |   ~~~~~^~~~~~~~~~~~~~
oneway.cpp:116:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |  scanf("%d",&p);
      |  ~~~~~^~~~~~~~~
oneway.cpp:118:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |   scanf("%d%d",&a,&b);
      |   ~~~~~^~~~~~~~~~~~~~

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