oj.uz

답안 #285989

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
285989 2020-08-29T21:16:36 Z Blagojce One-Way Streets (CEOI17_oneway) C++11
0 / 100
 4 ms 5376 KB 
#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;

const ll inf = 1e18;
const ld eps = 1e-13;
const ll mod = 1e9+7; 
const int i_inf = 1e9;
const int mxn = 1e5;
mt19937 _rand(time(NULL));
clock_t timer = clock();

int n, m;
vector<pii> g[mxn];
int ans[mxn];
int dep[mxn];
bool vis[mxn];
bool bridge[mxn];


void dfs0(int u, int ed){
	vis[u] = true;
	int mindepth = dep[u];
	for(auto e : g[u]){
		if(e.nd == ed) continue;
		if(!vis[e.st]){
			dep[e.st] = dep[u] + 1;
			dfs0(e.st, e.nd);
		}
		mindepth = min(mindepth, dep[e.st]);
	}
	if(mindepth >= dep[u]){
		bridge[ed] = true;
	}
	else{
		dep[u] = mindepth;
	}
}

int group[mxn];
void dfs1(int u, int col){
	vis[u] = true;
	group[u] = col;
	for(auto e : g[u]){
		if(vis[e.st] || bridge[e.nd]) continue;
		dfs1(e.st, col);
	}
}
vector<pii> tree[mxn];

int par[mxn];
int uped[mxn];
int sparse[mxn][20];
int depth[mxn];

void dfs2(int u){
	vis[u] = true;
	sparse[u][0] = par[u];
	fr(i, 1, 20) sparse[u][i] = sparse[sparse[u][i-1]][i-1];
	for(auto e : tree[u]){
		if(vis[e.st]) continue;
		par[e.st] = u;
		depth[e.st] = depth[u] + 1;
		uped[e.st] = e.nd;
		dfs2(e.st);
	}
}
int lca(int a, int b){
	int d = min(depth[a], depth[b]);
	for(int i = 19; i >= 0; i --){
		if(depth[a] - (1<<i) >= d) a = sparse[a][i];
		if(depth[b] - (1<<i) >= d) b = sparse[b][i];
	}
	if(a == b) return a;
	for(int i = 19; i >= 0; i --){
		if(sparse[a][i] != sparse[b][i]){
			a = sparse[a][i];
			b = sparse[b][i];
		}
	}
	return sparse[a][0];
}
void solve(){
	cin >> n >> m;
	int l[m], r[m];
	fr(i, 0, m){
		int u, v;
		cin >> u >> v;
		--u, --v;
		
		l[i] = u;
		r[i] = v;
		
		if(u == v){
			continue;
		}
		g[u].pb({v, i});
		g[v].pb({u, i});
	}
	fr(i, 0, n){
		if(vis[i]) continue;
		dfs0(i, -1);
	}
	memset(vis, false, sizeof(vis));
	int col = 0;
	fr(i, 0, n){
		if(vis[i]) continue;
		dfs1(i, col);
		++col;
	}
	fr(i, 0, m){
		if(!bridge[i] || l[i] == r[i]) continue;

		int a = group[l[i]];
		int b = group[r[i]];
		
		tree[a].pb({b, i+1});
		tree[b].pb({a, -(i+1)});
	}
	memset(vis, false, sizeof(vis));
	fr(i, 0, col){
		if(vis[i]) continue;
		par[i] = i;
		uped[i] = 0;
		dfs2(i);
	}
	int p;
	cin >> p;
	bool answered[mxn];
	memset(answered, false, sizeof(answered));
	fr(i, 0, p){
		int u, v;
		cin >> u >> v;
		--u, --v;
		u = group[u];
		v = group[v];
		if(u == v) continue;
		
		int k = lca(u, v);
		
		
		while(!answered[u] || depth[u] > depth[k]){
			if(uped[u] == 0) break;
			
			if(uped[u] < 0){
				ans[(-uped[u])-1] = 1;
			}
			if(uped[u] > 0){
				ans[uped[u]-1] = 2;
			}
			answered[u] = true;
			u = par[u];
		}
		while(!answered[v] || depth[v] > depth[k]){
			if(uped[v] == 0) break;
			
			if(uped[v] < 0){
				ans[(-uped[v])-1] = 2;
			}
			if(uped[v] > 0){
				ans[uped[v]-1] = 1;
			}
			answered[v] = true;
			v = par[v];
		}
	}
	fr(i, 0, m){
		if(ans[i] == 0) cout<<'B';
		else if(ans[i] == 1) cout<<'R';
		else cout<<'L';
	}
	cout<<endl;
	
}

int main(){
	solve();
}

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5248 KB Output is correct
2 Correct 3 ms 5248 KB Output is correct
3 Correct 4 ms 5376 KB Output is correct
4 Incorrect 4 ms 5376 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5248 KB Output is correct
2 Correct 3 ms 5248 KB Output is correct
3 Correct 4 ms 5376 KB Output is correct
4 Incorrect 4 ms 5376 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5248 KB Output is correct
2 Correct 3 ms 5248 KB Output is correct
3 Correct 4 ms 5376 KB Output is correct
4 Incorrect 4 ms 5376 KB Output isn't correct
5 Halted 0 ms 0 KB -