Submission #1025775

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025775		Taxiradio	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	237 ms	37820 KiB

oneway

// Source: https://usaco.guide/general/io

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

vector<array<int , 2>> es;
vector<vector<array<int , 2>>> g1;
vector<int> comp , l, ti;
stack<int> u;
int t = 1 , c = 0; 

void dfs(int p , int b){
	l[p] = ti[p] = t++;
	u.push(p);
	for(auto [x , i]: g1[p]){
		if(b == i)continue;
		if(ti[x] == 0){
			dfs(x , i);
			if(l[x] > ti[p]){
				while(true){
					comp[u.top()] = c;
					if(u.top() == x){
						u.pop();
						break;
					}
					u.pop();
				}
				c++;
			}
			l[p] = min(l[p] , l[x]);
			continue;
		}
		l[p] = min(l[p] , ti[x]);
	}
}

vector<vector<array<int , 2>>> g2;
vector<bool> vis;

void dfs(int p){
	vis[p] = 1;
	for(auto [x , i]: g1[p]){
		if(vis[x])continue;
		if(comp[x] != comp[p]){
			g2[comp[x]].push_back({comp[p] , i});
			g2[comp[p]].push_back({comp[x] , i});
			//cout << comp[x] << " " << comp[p] << endl;
		}
		dfs(x);
	}
}

vector<array<int , 28>> bl;
vector<int> f;
vector<array<int , 2>> k;
void bls(int p , int e , int y){
	bl[p][0] = e;
	//cout << p << " " << e << endl;
	if(e==-1)f[p] = 0;else f[p] = f[e]+1;
	k[p][0] = e;
	k[p][1] = y;
	for(int i = 1; i < 28; i++){
		if(bl[p][i-1] == -1){
			bl[p][i] = -1;
			continue;
		}
		bl[p][i] = bl[bl[p][i-1]][i-1];
	}
	for(auto [x, i] : g2[p]){
		if(x==e)continue;
		bls(x , p , i);
	}
}

int get(int a , int b){
	if(f[a] < f[b])swap(a , b);
	for(int i = 27; i >=0; i--){
		if((1<<i) <= f[a]-f[b])a = bl[a][i];
	}
	if(a==b)return a;
	for(int i = 27; i >=0; i--){
		if(bl[a][i] != bl[b][i]){
			a = bl[a][i];
			b = bl[b][i];
		}
	}
	return bl[a][0];
}
vector<array<int , 3>> v;
vector<int> ans;
void solve(int i){
	//cout << v[i][0] << " " << v[i][1] << " " << v[i][2] << endl;
	int a = v[i][1];
	while(f[a] != v[i][0]){
		if(ans[k[a][1]] != 0)break;
		//cout << a << " " << k[a][0] << " " << k[a][1] << endl;
		if(comp[es[k[a][1]][0]] == a){
			ans[k[a][1]] = v[i][2];
		}else{
			ans[k[a][1]] = v[i][2]*-1;
		}
		a = k[a][0];
	}
}

int main() {
	int n , m; cin >> n >> m;
	g1.resize(n);
	comp.resize(n);
	l.resize(n);
	ti.resize(n);
	for(int i = 0; i < m; i++){
		int a , b; cin >> a >> b;
		g1[a-1].push_back({b-1 , i});
		g1[b-1].push_back({a-1 , i});
		es.push_back({a-1 , b-1});
	}
	vis.resize(n , false);
	g2.resize(n);
	bl.resize(n);
	k.resize(n);
	f.resize(n);
	for(int i = 0; i < n; i++){
		if(ti[i] == 0){
			dfs(i , -1);
			while(!u.empty()){
				comp[u.top()] = c;
				u.pop();
			}
			c++;
			dfs(i);
			bls(comp[i] , -1 , -1);
		}
	}
	/*
	for(int i = 0; i < n; i++){
		cout << comp[i] << " ";
	}
	*/
	int q; cin >> q;
	for(int i = 0; i < q; i++){
		int a , b; cin >> a >> b;
		a--;
		b--;
		int d = get(comp[a] , comp[b]);
		v.push_back({f[d] , comp[a] , -1});
		v.push_back({f[d] , comp[b] , 1});
	}
	sort(v.begin() , v.end());
	ans.resize(m, 0);
	for(int i = 0; i < v.size(); i++){
		solve(i);
	}
	//cout << "a "<<endl;
	for(int x : ans){
		if(x == 0)cout << "B";
		if(x == 1)cout << "L";
		if(x == -1)cout << "R";
	}
	cout << endl;
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:151:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |  for(int i = 0; i < v.size(); i++){
      |                 ~~^~~~~~~~~~

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