oj.uz

Submission #374730

# Submission time Handle Problem Language Result Execution time Memory
374730 2021-03-08T03:35:24 Z YJU One-Way Streets (CEOI17_oneway) C++14
100 / 100
 324 ms 38508 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll N=1e5+5;
const ll MOD=1e9+7;
#define REP(i,n) for(int i=0;i<n;++i)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
 
ll n,m,q,x,y;
vector<ll> v[N];
pll ed[N];
ll ans[N];
 
ll depth[N],low[N],vis[N],color[N],is_bridge[N];
 
void DFS(ll nd,ll par,ll par_edge){
	vis[nd]=1;
	low[nd]=depth[nd]=depth[par]+1;
	for(auto i:v[nd]){
		if(i==par_edge)continue;
		ll to=ed[i].X+ed[i].Y-nd;
		if(vis[to]){
			low[nd]=min(low[nd],depth[to]);
		}else{
            DFS(to,nd,i);
            low[nd]=min(low[nd],low[to]);
		}
	}
	if(low[nd]>=depth[nd]){
		is_bridge[par_edge]=1;
	}
}
 
void coloring(ll nd,ll pa,ll par_edge,ll C){
	vis[nd]=1;color[nd]=C;
    for(auto i:v[nd]){
		if(i==par_edge)continue;
		ll to=ed[i].X+ed[i].Y-nd;
		if(vis[to])continue;
		coloring(to,nd,i,C);
    }
}
 
ll ti,anc[N][20],pe[N];
 
void dfs(ll nd,ll pa,ll par_edge){
	vis[nd]=1;
 	depth[nd]=depth[pa]+1;
    pe[nd]=par_edge;
    anc[nd][0]=pa;
    REP1(i,18)anc[nd][i]=anc[anc[nd][i-1]][i-1];
 
    for(ll i:v[nd]){
		if(i==par_edge)continue;
		ll to=(ed[i].X+ed[i].Y)-nd;
		dfs(to,nd,i);
    }
}
 
ll lca(ll nda,ll ndb){
	if(depth[nda]<depth[ndb])swap(nda,ndb);
	for(int i=18;i>=0;i--){
		if(depth[anc[nda][i]]>=depth[ndb])nda=anc[nda][i];
	} 
	if(nda==ndb)return nda;
	for(int i=18;i>=0;i--){
		if(anc[nda][i]!=anc[ndb][i]){
			nda=anc[nda][i];ndb=anc[ndb][i];
		}
	}
    return anc[nda][0];
}
 
ll u[N],d[N];
 
void build(ll nd,ll pa,ll par_edge){
	vis[nd]=1;
	for(auto i:v[nd]){
		if(i==par_edge)continue;
		ll to=(ed[i].X+ed[i].Y)-nd;
		build(to,nd,i);
		u[nd]+=u[to];
		d[nd]+=d[to];
	}
	if(u[nd])ans[par_edge]=nd;
	if(d[nd])ans[par_edge]=pa;
}
 
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	memset(ans,-1,sizeof(ans));
	//reset
	//
	cin>>n>>m;
	REP1(i,m){
		cin>>ed[i].X>>ed[i].Y;
		if(ed[i].X!=ed[i].Y){
			v[ed[i].X].pb(i);
			v[ed[i].Y].pb(i);
		}
	}
	
	memset(vis,0,sizeof(vis));
	REP1(i,n){
		if(!vis[i])DFS(i,0,0);
	}
	
    REP1(i,n)v[i].clear();
	REP1(i,m)if(!is_bridge[i]&&ed[i].X!=ed[i].Y)v[ed[i].X].pb(i),v[ed[i].Y].pb(i);
	memset(vis,0,sizeof(vis));
    REP1(i,n){
		if(!vis[i])coloring(i,0,0,i);
    }
    REP1(i,n)v[i].clear();
 
    REP1(i,m){
		if(is_bridge[i]){
			ed[i].X=color[ed[i].X];
			ed[i].Y=color[ed[i].Y];
			assert(ed[i].X!=ed[i].Y);
            v[ed[i].X].pb(i);v[ed[i].Y].pb(i);
		}
    }
 
    REP1(i,n)assert(color[i]>0);
    memset(vis,0,sizeof(vis));
    REP1(i,n){
    	if(!vis[color[i]]){
    		dfs(color[i],0,0);
		}
	}
 
	cin>>q;
	while(q--){
		cin>>x>>y;
        x=color[x];y=color[y];
        if(x==y)continue;
        ll L=lca(x,y);
        if(L!=x){
			++u[x];--u[L];
        }
        if(L!=y){
			++d[y];--d[L];
        }
	}
 
 	memset(vis,0,sizeof(vis));
 	REP1(i,n){
 		if(!vis[color[i]]){
 			build(color[i],0,0);
		}
	}
 
	REP1(i,m){
		if(is_bridge[i]){
			cout<<(ans[i]==-1?"B":(ans[i]==ed[i].X?"R":"L"));
		}else{
			cout<<"B";
		}
		if(i==m)cout<<"\n";
	}
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4332 KB Output is correct
2 Correct 3 ms 4332 KB Output is correct
3 Correct 3 ms 4460 KB Output is correct
4 Correct 4 ms 4588 KB Output is correct
5 Correct 4 ms 4588 KB Output is correct
6 Correct 3 ms 4332 KB Output is correct
7 Correct 4 ms 4588 KB Output is correct
8 Correct 4 ms 4588 KB Output is correct
9 Correct 3 ms 4460 KB Output is correct
10 Correct 4 ms 4460 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4332 KB Output is correct
2 Correct 3 ms 4332 KB Output is correct
3 Correct 3 ms 4460 KB Output is correct
4 Correct 4 ms 4588 KB Output is correct
5 Correct 4 ms 4588 KB Output is correct
6 Correct 3 ms 4332 KB Output is correct
7 Correct 4 ms 4588 KB Output is correct
8 Correct 4 ms 4588 KB Output is correct
9 Correct 3 ms 4460 KB Output is correct
10 Correct 4 ms 4460 KB Output is correct
11 Correct 67 ms 11372 KB Output is correct
12 Correct 67 ms 14572 KB Output is correct
13 Correct 84 ms 23040 KB Output is correct
14 Correct 119 ms 30188 KB Output is correct
15 Correct 128 ms 32112 KB Output is correct
16 Correct 156 ms 31980 KB Output is correct
17 Correct 142 ms 33876 KB Output is correct
18 Correct 168 ms 31980 KB Output is correct
19 Correct 130 ms 35180 KB Output is correct
20 Correct 66 ms 12396 KB Output is correct
21 Correct 55 ms 14572 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4332 KB Output is correct
2 Correct 3 ms 4332 KB Output is correct
3 Correct 3 ms 4460 KB Output is correct
4 Correct 4 ms 4588 KB Output is correct
5 Correct 4 ms 4588 KB Output is correct
6 Correct 3 ms 4332 KB Output is correct
7 Correct 4 ms 4588 KB Output is correct
8 Correct 4 ms 4588 KB Output is correct
9 Correct 3 ms 4460 KB Output is correct
10 Correct 4 ms 4460 KB Output is correct
11 Correct 67 ms 11372 KB Output is correct
12 Correct 67 ms 14572 KB Output is correct
13 Correct 84 ms 23040 KB Output is correct
14 Correct 119 ms 30188 KB Output is correct
15 Correct 128 ms 32112 KB Output is correct
16 Correct 156 ms 31980 KB Output is correct
17 Correct 142 ms 33876 KB Output is correct
18 Correct 168 ms 31980 KB Output is correct
19 Correct 130 ms 35180 KB Output is correct
20 Correct 66 ms 12396 KB Output is correct
21 Correct 55 ms 14572 KB Output is correct
22 Correct 324 ms 35052 KB Output is correct
23 Correct 257 ms 33244 KB Output is correct
24 Correct 246 ms 33132 KB Output is correct
25 Correct 313 ms 38508 KB Output is correct
26 Correct 276 ms 34760 KB Output is correct
27 Correct 242 ms 33132 KB Output is correct
28 Correct 39 ms 9324 KB Output is correct
29 Correct 96 ms 13164 KB Output is correct
30 Correct 100 ms 13824 KB Output is correct
31 Correct 88 ms 13548 KB Output is correct
32 Correct 213 ms 28012 KB Output is correct