Submission #490965

#	Time	Username	Problem	Language	Result	Execution time	Memory
490965		minhcool	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	2 ms	5068 KiB

oneway

#include<bits/stdc++.h>

using namespace std; 

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define eb emplace_back
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 2e5 + 5, MAXN = 1e7 + 5;
 
const long long oo = 1e18 + 7, mod = 1e9 + 7;

int n, m, p;
vector<int> Adj[N];

int times[N], low[N];

int l[N], r[N];

map<ii, int> edges;
vector<ii> ques;

int sparse1[N][20], sparse2[N][20];

char ans[N];

int cntt = 0;

void dfs(int u, int p, int root){
    cntt++;
	times[u] = low[u] = cntt;
	l[u] = cntt;
	//vector<int> child;
	for(auto v : Adj[u]){
		if(!times[v]){
		    //child.pb(v);
			dfs(v, u, root);
			//cout << u << " " << v << "\n";
			//cout << low[u] << " " << low[v] << " " << times[u] << " " << times[v] << "\n";
			if(low[v] <= times[u]){
			    //cout << u << " " << v << "\n";
				ans[edges[{min(u, v), max(u, v)}]] = 'B';
			}
			else low[u] = min(low[u], low[v]);
		}
		else if(v != p){
		    low[u] = min(low[u], times[v]);
		    ans[edges[{min(u, v), max(u, v)}]] = 'B';
		}
	}
	r[u] = cntt;
}

void prep(){
	for(int i = 1; i <= n; i++) sparse2[i][0] = oo;
	for(auto it : ques){
		int temp1 = it.fi, temp2 = it.se;
		if(times[temp1] > times[temp2]) swap(times[temp1], times[temp2]);
		sparse1[temp1][0] = max(sparse1[temp1][0], temp2);
		sparse2[temp2][0] = min(sparse2[temp2][0], temp1);
	}
	for(int i = 1; i <= 18; i++){
		for(int j = 1; (j + (1LL << i) - 1) <= n; j++){
			sparse1[j][i] = max(sparse1[j][i - 1], sparse1[j + (1LL << (i - 1))][i - 1]);
			sparse2[j][i] = min(sparse2[j][i - 1], sparse2[j + (1LL << (i - 1))][i - 1]);
		}
	}
}

int get_mx(int l, int r){
	int k = log2(r - l + 1);
	return max(sparse1[l][k], sparse1[r - (1LL << k) + 1][k]);
}

int get_mn(int l, int r){
	int k = log2(r - l + 1);
	return min(sparse2[l][k], sparse2[r - (1LL << k) + 1][k]);
}

map<ii, vector<int>> cnt;

void process(){
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
	    int x, y;
	    cin >> x >> y;
	    cnt[{min(x, y), max(x, y)}].pb(i);
	}
	for(auto it : cnt){
	    int x = it.fi.fi, y = it.fi.se;
	    if(x == y){
	        ans[it.se[0]] = 'B';
	        continue;
	    }
	    Adj[x].pb(y);
	    Adj[y].pb(x);
	    if(it.se.size() > 1){
	        for(auto it1 : it.se) ans[it1] = 'B';
	        continue;
	    }
		edges[{min(x, y), max(x, y)}] = it.se[0];
	}
	cin >> p;
	for(int i = 1; i <= p; i++){
		int u, v;
		cin >> u >> v;
		ques.pb({u, v});
	}
	dfs(1, 1, 1);
	prep();
	for(auto it : edges){
		if(ans[it.se] == 'B') continue;
		int templ = max(l[it.fi.fi], l[it.fi.se]), tempr = min(r[it.fi.fi], r[it.fi.se]);
		int temp1 = get_mx(templ, tempr), temp2 = get_mn(templ, tempr);
		if(temp1 > tempr) ans[it.se] = (l[it.fi.fi] < l[it.fi.se] ? 'R' : 'L');
		else if(temp2 < templ) ans[it.se] = (l[it.fi.fi] < l[it.fi.se] ? 'L' : 'R');
		else ans[it.se] = 'B';
	} 
	for(int i = 1; i <= m; i++) cout << ans[i];
}
 
signed main(){
	ios_base::sync_with_stdio(0);
/*
	#ifdef nqm
		freopen("input.inp", "r", stdin);
		freopen("output.out", "w", stdout);
	#endif
	#ifndef nqm
		
	#endif
*/
	process();
}

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