Submission #585012

#	Time	Username	Problem	Language	Result	Execution time	Memory
585012		amunduzbaev	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	16 ms	25044 KiB

oneway

#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]);
		}
	}
	//~ cout<<u<<" "<<tin[u]<<" "<<fup[u]<<endl;
	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()) swap(sub[u], sub[v]);
		for(auto el : sub[v]){
			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);
		}
	}
	
	//~ cout<<u<<" : ";
	//~ for(auto x : sub[u]) cout<<x<<" ";
	//~ cout<<endl;
	
	if(sub[u].empty() && ~p){
		is[p] = 2;
	} else if(~p) {
		if(*sub[u].begin() < 0 && (*--sub[u].end()) > 0){
			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;
			}
		}
	}
	
	//~ for(int i=1;i<=n;i++){
		//~ cout<<cmp[i]<<" ";
	//~ } cout<<endl;
	
	//~ for(int i=1;i<=cur;i++){
		//~ for(auto x : davka[i]){
			//~ int v = cmp[a[x]] ^ cmp[b[x]] ^ i;
			//~ cout<<i<<" "<<v<<" "<<x<<endl;
		//~ }
	//~ }
	
	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
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40