제출 #739423

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
739423		Iliya_	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	3 ms	5844 KiB

oneway

// IN THE NAME OF GOD
#include<bits/stdc++.h>
#define endl '\n'
#define file_reading freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define flush cout.flush();
using namespace std;
typedef long long ll;
typedef long double dll;
typedef unsigned long long ull;

const int N = 1e5+7, inf = 1e9, logg = 23;
vector<pair<int,int>> g[N], t[N]; 
int ma[N], ma2[N], ans[N], e[N][2], mn[N], h[N], b[N], par[N][logg], tim[N][2], dat[N], use[N], now, cnt; 

void dfs(int v, int ed, int fa){
	ma[v]++; 
	par[v][0] = fa; 
	for(int i=1; i<logg; i++) par[v][i] = par[par[v][i-1]][i-1]; 
	tim[v][0] = ++now; 
	for(pair<int,int> cur : g[v]){
		int u = cur.first, w = cur.second; 
		if (!ma[u]){
			h[u] = h[v]+1;
			t[e[w][0]].push_back({e[w][1],++cnt});
			t[e[w][1]].push_back({e[w][0],cnt}); 
			dat[cnt] = w; 
			dfs(u,w,v); 
			mn[v] = min(mn[v],mn[u]); 
			if (mn[u] <= h[v]) ans[w] = 2; 
			ma2[w]++; 
		}
		else if (w != ed && !ma2[w]) mn[v] = min(mn[v], h[u]), ans[w] = 2, ma2[w]++;
	}
	tim[v][1] = ++now; 
}

void dfs2(int v, int ed){
	ma[v]++; 
	for(pair<int,int> cur : t[v]){
		int u = cur.first, w = cur.second; 
		if (ma[u] != 2){
			h[u] = h[v] + 1; 
			dfs2(u,w); 
			if (mn[v] > mn[u]) mn[v] = mn[u], use[v] = use[u]; 
			if (mn[u] <= h[v]) b[w] = 1; 
			ma2[w]++; 
		}
		else if (w != ed && ma2[w] != 2){
			if (mn[v] > h[u]) mn[v] = h[u], use[v] = w; 
			b[w] = 1; 
			ma2[w]++; 
		}
	}
}

bool is(int v, int u){
	if (tim[v][0] <= tim[u][0] && tim[v][1] >= tim[u][1]) return 1; 
	else return 0; 
}

int lca(int v, int u){
	if (v == u) return v; 
	if (h[v] < h[u]) swap(v,u); 
	for(int i=logg-1; i>=0; i--) if (par[v][i] != 0) v = (!is(par[v][i],u) ? par[v][i] : v); 
	return par[v][0]; 
}

int32_t main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);	
	
	int n,m; cin >> n >> m; 
	for(int i=1; i<=m; i++){
		cin >> e[i][0] >> e[i][1]; 
		if (e[i][0] == e[i][1]) ans[i] = 2; 
		else g[e[i][0]].push_back({e[i][1],i}), g[e[i][1]].push_back({e[i][0],i});
	}	
	fill(mn,mn+N,inf); 
	for(int i=1; i<=n; i++) if (!ma[i]) mn[i] = h[i], dfs(i,0,0);
	int q; cin >> q; 
	while(q--){
		int v,u; cin >> v >> u; 
		int f = lca(v,u);
		t[v].push_back({f,++cnt});
		t[f].push_back({v,cnt}); 
		dat[cnt] = 0; 
		t[u].push_back({f,++cnt}); 
		t[f].push_back({u,cnt});
		dat[cnt] = 0; 
	}
	fill(h,h+N,0);
	fill(mn,mn+N,inf);
	for(int i=1; i<=n; i++) if (ma[i] != 2) mn[i] = h[i], dfs2(i,0);  
	for(int i=1; i<=cnt; i++){
		if (!dat[i] || ans[dat[i]] == 2) continue; 
		if (!b[i]) ans[dat[i]] = 2; 
		else{
			int v = e[dat[i]][0], u = e[dat[i]][1];  
			if (h[v] < h[u]) swap(v,u); 
			if (((use[v]-(n-1))&1) == 0) ans[dat[i]] = (h[e[dat[i]][0]] < h[e[dat[i]][1]] ? 0 : 1); 
			else ans[dat[i]] = (h[e[dat[i]][0]] > h[e[dat[i]][1]] ? 0 : 1); 
		}
	}
	for(int i=1; i<=m; i++) cout << (ans[i] == 2 ? 'B' : (ans[i] == 0 ? 'R' : 'L')); 
	cout << endl; 

	return 0;
}

/* think of these first
* graph : dfs, bfs, dsu, mst, dijkstra, turEuler, lca, scc, trie
* dp : simple, bitmask
* divide and conquer
* greedy
* bitwise
* bianry search
* strings approch : kmp, hash
* combination
* segment, lazy, RMQ
*/

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