Submission #1221688

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221688		vako_p	One-Way Streets (CEOI17_oneway)	C++20	30 / 100	332 ms	270428 KiB

oneway

#include <bits/stdc++.h> 
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define sd second
#define debug(x) cerr << #x << "----> " << x << endl;
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("O3")

const int mxN = 1e6 + 5;
ll n,m,x[mxN],y[mxN],vis[mxN],ans[mxN],par1[mxN],p[mxN][20],tt,tt1,pp[2][mxN],aa[mxN],in[mxN],in1[mxN],out[mxN];
vector<ll> v[mxN],vv1,v1[mxN],roots;
vector<pair<ll,ll>> vv;
map<ll,ll> mp[mxN],mp1[mxN],viss1[mxN],viss[mxN];

struct ds{
	vector<ll> rank,par;
	
	void init(){
		rank.assign(n + 5, 0LL);
		par.resize(n + 5);
		for(int i = 0; i < n + 5; i++) par[i] = i;
	}
	
	ll find(ll at){
		if(par[at] == at) return at;
		par[at] = find(par[at]);
		return par[at];
	}
	
	void merge(ll a, ll b){
		a = find(a);
		b = find(b);
		if(a == b) return;
		if(rank[a] < rank[b]) swap(a, b);
		par[b] = a;
		rank[a] += (rank[a] == rank[b]);
		if(in1[par1[b]] < in1[par1[a]]) par1[a] = par1[b];
	}
};

ds s;

void dfs2(ll at, ll par){
	if(vis[at]) return;
	par1[at] = par;
	in1[at] = tt1++;
	vv1.pb(at);
	vis[at] = 1;
	for(auto it : v[at]){
//		cout << at << "----------> " << it << ' ' << viss[at][it] << '\n';
		if(vis[it] == 2 or (it == par and !viss[at][it])) continue;
		else if(vis[it] == 1) vv.pb({at, it});
		else dfs2(it, at);
	}
	vis[at] = 2;
}
 
void dfs(ll at, ll par){
//	cout << at << ' ' << par << endl;
	in[at] = tt++;
	p[at][0] = par;
	for(int i = 1; i < 20; i++) p[at][i] = p[p[at][i - 1]][i - 1];
	for(auto it : v1[at]){
		if(it == par) continue;
		dfs(it, at);
	}
	out[at] = tt;
}

bool check(ll a, ll b){
	return (in[a] <= in[b] and out[a] >= out[b]);
}

ll lca(ll a, ll b){
	if(check(a, b)) return a;
	for(int i = 19; i >= 0; i--){
		if(!check(p[a][i], b)) a = p[a][i];
	}
	return p[a][0];
}

void dfs3(ll at, ll par){
	for(auto it : v1[at]){
		if(it == par) continue;
		dfs3(it, at);
		pp[0][at] += pp[0][it];
		pp[1][at] += pp[1][it];
	}
	assert(!pp[0][at] or !pp[1][at]);
	if(pp[0][at]) ans[mp1[at][par]] = (aa[mp1[at][par]] == at);
	if(pp[1][at]) ans[mp1[at][par]] = 1 - (aa[mp1[at][par]] == at);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	s.init();
	for(int i = 0; i < m; i++){
		ll a,b;
		ans[i] = 2;
		cin >> a >> b;
		aa[i] = a;
		if(viss1[a][b]) viss[a][b] = viss[b][a] = true;
		viss1[a][b] = viss1[b][a] = true;
		mp[a][b] = mp[b][a] = i;
		v[a].pb(b);
		v[b].pb(a);
	}
	ll q;
	cin >> q;
	for(int i = 0; i < q; i++) cin >> x[i] >> y[i];
	for(int i = 1; i <= n; i++){
		if(vis[i]) continue;
		vv.clear();
		vv1.clear();
		dfs2(i, i);
		for(auto it1 : vv){
			ll at = s.find(it1.ff),it = s.find(it1.sd);
			while(s.find(at) != s.find(it)){
				s.merge(at, par1[at]);
				at = s.find(at);
			}
		}
		for(auto at : vv1){
			for(auto it : v[at]){
				if(s.find(it) == s.find(at)) continue;
				mp1[s.find(at)][s.find(it)] = mp[at][it];
				aa[mp[at][it]] = s.find(aa[mp[at][it]]);
				v1[s.find(at)].pb(s.find(it));
			}
		}
		ll root = s.find(i);
		roots.pb(root);
		dfs(root, root);
	}
	for(int i = 0; i < q; i++){
		x[i] = s.find(x[i]);
		y[i] = s.find(y[i]);
		ll at = lca(x[i], y[i]);
		pp[0][at]--;
		pp[1][at]--;
		pp[0][x[i]]++;
		pp[1][y[i]]++;
	}
	for(int i = 1; i <= n; i++) vis[i] = 0;
	for(auto it : roots) dfs3(it, it);
	char ch[] = {'L', 'R', 'B'};
	for(int i = 0; i < m; i++) cout << ch[ans[i]];
}

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