oj.uz

Submission #285991

# Submission time Handle Problem Language Result Execution time Memory
285991 2020-08-29T21:19:10 Z Blagojce One-Way Streets (CEOI17_oneway) C++11
60 / 100
 3000 ms 26872 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(depth[u] > depth[k]){
			if(uped[u] == 0) break;
			
			if(uped[u] < 0){
				ans[(-uped[u])-1] = 1;
			}
			else{
				ans[uped[u]-1] = 2;
			}
			answered[u] = true;
			u = par[u];
		}
		while(depth[v] > depth[k]){
			if(uped[v] == 0) break;
			
			if(uped[v] < 0){
				ans[(-uped[v])-1] = 2;
			}
			else{
				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
30.0 / 30.0

# Verdict Execution time Memory 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 Correct 5 ms 5376 KB Output is correct
5 Correct 5 ms 5504 KB Output is correct
6 Correct 5 ms 5376 KB Output is correct
7 Correct 6 ms 5504 KB Output is correct
8 Correct 5 ms 5504 KB Output is correct
9 Correct 5 ms 5376 KB Output is correct
10 Correct 5 ms 5376 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory 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 Correct 5 ms 5376 KB Output is correct
5 Correct 5 ms 5504 KB Output is correct
6 Correct 5 ms 5376 KB Output is correct
7 Correct 6 ms 5504 KB Output is correct
8 Correct 5 ms 5504 KB Output is correct
9 Correct 5 ms 5376 KB Output is correct
10 Correct 5 ms 5376 KB Output is correct
11 Correct 156 ms 11000 KB Output is correct
12 Correct 144 ms 11896 KB Output is correct
13 Correct 166 ms 13308 KB Output is correct
14 Correct 175 ms 16632 KB Output is correct
15 Correct 180 ms 18036 KB Output is correct
16 Correct 244 ms 24656 KB Output is correct
17 Correct 255 ms 25976 KB Output is correct
18 Correct 217 ms 24952 KB Output is correct
19 Correct 255 ms 26872 KB Output is correct
20 Correct 142 ms 11640 KB Output is correct
21 Correct 141 ms 11768 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory 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 Correct 5 ms 5376 KB Output is correct
5 Correct 5 ms 5504 KB Output is correct
6 Correct 5 ms 5376 KB Output is correct
7 Correct 6 ms 5504 KB Output is correct
8 Correct 5 ms 5504 KB Output is correct
9 Correct 5 ms 5376 KB Output is correct
10 Correct 5 ms 5376 KB Output is correct
11 Correct 156 ms 11000 KB Output is correct
12 Correct 144 ms 11896 KB Output is correct
13 Correct 166 ms 13308 KB Output is correct
14 Correct 175 ms 16632 KB Output is correct
15 Correct 180 ms 18036 KB Output is correct
16 Correct 244 ms 24656 KB Output is correct
17 Correct 255 ms 25976 KB Output is correct
18 Correct 217 ms 24952 KB Output is correct
19 Correct 255 ms 26872 KB Output is correct
20 Correct 142 ms 11640 KB Output is correct
21 Correct 141 ms 11768 KB Output is correct
22 Execution timed out 3082 ms 26104 KB Time limit exceeded
23 Halted 0 ms 0 KB -