oj.uz

Submission #585037

# Submission time Handle Problem Language Result Execution time Memory
585037 2022-06-28T09:15:54 Z amunduzbaev One-Way Streets (CEOI17_oneway) C++17
0 / 100
 8 ms 12372 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef int64_t ll;
//~ #define int ll

const int N = 1e5 + 5;
vector<int> edges[N], davka[N], qq[N];
vector<int> ss;
int a[N], b[N], fup[N];
int t, used[N], tin[N];
int cmp[N], cur, is[N];

void dfs(int u, int p = -1){
	used[u] = 1;
	tin[u] = fup[u] = ++t;
	ss.push_back(u);
	for(auto x : edges[u]){
		if(x == p) continue;
		int v = a[x] ^ b[x] ^ u;
		if(used[v]){
			fup[u] = min(fup[u], tin[v]);
		} else {
			dfs(v, x);
			fup[u] = min(fup[u], fup[v]);
		}
	}
	
	if(tin[u] == fup[u]){
		int x; cur++;
		do{
			x = ss.back(); ss.pop_back();
			cmp[x] = cur;
		}while(x != u);
	}
}

set<int> sub[N];
void dfs_stol(int u, int p = -1){
	used[u] = 1;
	for(auto x : davka[u]){
		if(x == p) continue;
		int v = cmp[a[x]] ^ cmp[b[x]] ^ u;
		dfs_stol(v, x);
		if(sub[v].size() > sub[u].size()) sub[u].swap(sub[v]); // swap(sub[u], sub[v]);
		for(auto el : sub[v]){
			if(sub[u].count(-el)) sub[u].erase(-el);
			else sub[u].insert(el);
		}
		sub[v].clear();
	}
	
	for(auto x : qq[u]){
		if(sub[u].count(-x)){
			sub[u].erase(-x);
		} else {
			sub[u].insert(x);
		}
	}
	
	if(sub[u].empty() && ~p){
		is[p] = 2;
	} else if(~p) {
		if(*sub[u].begin() < 0 && 0 < (*--sub[u].end())){
			assert(false);
		}
		
		if(*sub[u].begin() > 0){
			is[p] = (a[p] == u);
		} else {
			is[p] = (b[p] == u);
		}
	}
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n, m; cin>>n>>m;
	for(int i=0;i<m;i++){
		cin>>a[i]>>b[i];
		edges[a[i]].push_back(i);
		edges[b[i]].push_back(i);
	}
	
	for(int i=1;i<=n;i++){
		if(used[i]) continue;
		dfs(i);
	}
	
	for(int i=1;i<=n;i++){
		for(auto x : edges[i]){ int v = a[x] ^ b[x] ^ i;
			if(cmp[i] != cmp[v]){
				davka[cmp[i]].push_back(x);
			} else {
				is[x] = 2;
			}
		}
	}
	
	int p; cin>>p;
	for(int i=1;i<=p;i++){
		int a, b; cin>>a>>b;
		qq[cmp[a]].push_back(i);
		qq[cmp[b]].push_back(-i);
	}
	
	memset(used, 0, sizeof used);
	for(int i=1;i<=cur;i++){
		if(used[i]) continue;
		dfs_stol(i);
	}
	
	for(int i=0;i<m;i++){
		if(is[i] == 0) cout<<"L";
		if(is[i] == 1) cout<<"R";
		if(is[i] == 2) cout<<"B";
	} cout<<"\n";
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 12372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 12372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 12372 KB Output isn't correct
2 Halted 0 ms 0 KB -