Submission #161578

#	Time	Username	Problem	Language	Result	Execution time	Memory
161578		amoo_safar	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	354 ms	41560 KiB

oneway

#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef string str;

const ll Mod = 1e9 + 7;
const int Maxn = 2e5 + 100;

ll par[Maxn];
ll get(ll u){
	if(u == par[u]) return u;
	return par[u] = get(par[u]);
}
void merge(ll u, ll v){
	u = get(u); v = get(v);
	par[u] = v;
	
}

vector<pll> G[Maxn];
vector<ll> H[Maxn];
vector< pll > ed, ed2;
ll ans[Maxn];
ll dep[Maxn];

ll DFS(ll u, ll d, ll p){
	dep[u] = d;
	ll hbk = d;
	ll adj, res;
	for(auto E : G[u]){
		if(E.S == p) continue;
		adj = E.F;
		if(dep[adj]){
			if(dep[adj] < d){merge(u, adj);
				hbk = min(hbk, dep[adj]);
			}	
		} else {
			//cerr << "! " << adj << " " << u << '\n';
			res = DFS(adj, d + 1, E.S);
			if(res != d + 1) merge(u, adj);
			else ed.pb({u, adj});
			hbk = min(hbk, res);
		}
	}
	return hbk;
}

ll sub[Maxn], va[Maxn], dep2[Maxn];
void dfs(ll u, ll p, ll d2){
	dep2[u] = d2;
	for(auto adj : H[u]){
		if(dep2[adj] == 0){
			dfs(adj, u, d2 + 1);
			va[u] += va[adj];
		}
	}
}
map<pll, ll> mp;

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	iota(par, par + Maxn, 0);
	ll n, m, p;
	cin >> n >> m;
	//assert(n == 5 && m == 6);
	//cout << "BBRBBL\n";
	//return 0;
	ll u, v;
	for(int i = 1; i <= m; i++){
		cin >> u >> v;
		mp[{u, v}] = i;
		G[u].pb({v, i});
		G[v].pb({u, i});
		ed2.pb({u, v});
	}
	for(int i = 1; i <= n; i++) if(dep[i] == 0) DFS(i, 1, -1);
	//for(int i = 1; i <= n; i++) cerr << get(i) << ' ';

	cin >> p;
	for(int i = 0; i < p; i++){
		cin >> u >> v;
		va[get(u)]++;
		va[get(v)]--;
	}
	
	for(auto x : ed2){
		if(get(x.F) == get(x.S)) continue;
		H[get(x.F)].pb(get(x.S));
		H[get(x.S)].pb(get(x.F));
	}
	for(int i = 1; i <= n; i++) if(get(i) == i && dep2[i] == 0) dfs(i, -1, 1);
	
	for(auto x : ed2){
		u = x.F; v = x.S;
		if(get(x.F) == get(x.S)) continue;
		assert(get(x.F) != get(x.S));
		//cerr << "! " << x.F << ' ' << x.S << '\n';
		//cerr << "!" << u << " " << v << '\n';
		if(dep2[get(u)] < dep2[get(v)]) swap(u, v);
		if(va[get(u)] == 0) continue;
		if(va[get(u)] < 0) swap(u, v);
		if(mp.count({u, v})) ans[mp[{u, v}]] = 1;
		else {
			assert( (mp[{v, u}] > 0) );
			ans[mp[{v, u}]] = 2;
		}
	}
	
	for(int i = 1; i <= m; i++) cout << "BRL"[ans[i]];
	cout << '\n';
	return 0;
}
/*
5 6
1 2
1 2
4 3
2 3
1 3
5 1
2
4 5
1 3


5 6
1 2
4 5
4 3
2 3
1 3
5 1
2
4 5
1 3

4 4
1 2
2 3
3 4
3 1
1
3 2


*/

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