oj.uz

Submission #374723

# Submission time Handle Problem Language Result Execution time Memory
374723 2021-03-08T02:47:57 Z YJU One-Way Streets (CEOI17_oneway) C++14
0 / 100
 3 ms 4352 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],stk[N],now,vis[N],color[N],is_bridge[N];

void DFS(ll nd,ll par,ll par_edge){
	vis[nd]=1;
	stk[++now]=nd;
	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,in[N],out[N],anc[N][20],pe[N];

void dfs(ll nd,ll pa,ll par_edge){

    pe[nd]=par_edge;
    anc[nd][0]=pa;
    REP1(i,18)anc[nd][i]=anc[anc[nd][i-1]][i-1];

    in[nd]=++ti;
    for(ll i:v[nd]){
		if(i==par_edge)continue;
		ll to=(ed[i].X+ed[i].Y)-nd;
		dfs(to,nd,i);
    }
    out[nd]=++ti;
}

bool is_anc(ll nda,ll ndb){
	return (in[nda]<=in[ndb]&&out[nda]>=out[ndb]);
}

ll lca(ll nda,ll ndb){

    if(is_anc(nda,ndb))return nda;
    if(is_anc(ndb,nda))return ndb;
    for(int i=18;i>=0;i--){
		if(!anc[nda][i])continue;
		if(!is_anc(anc[nda][i],ndb)){
			nda=anc[nda][i];
		}
    }
    return anc[nda][0];
}

ll u[N],d[N];

void build(ll nd,ll pa,ll par_edge){
	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;
		v[ed[i].X].pb(i);
		v[ed[i].Y].pb(i);
	}
	DFS(1,0,0);
    REP1(i,n)v[i].clear();
	memset(vis,0,sizeof(vis));
	REP1(i,m)if(!is_bridge[i])v[ed[i].X].pb(i),v[ed[i].Y].pb(i);
    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)cout<<color[i]<<(i==n?"\n":" ");

    dfs(1,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];
        }*/
        while(L!=x)ans[pe[x]]=x,x=anc[x][0];
        while(L!=y)ans[pe[y]]=anc[y][0],y=anc[y][0];
	}

	//build(1,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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4352 KB Output isn't correct
2 Halted 0 ms 0 KB -