oj.uz

Submission #585044

# Submission time Handle Problem Language Result Execution time Memory
585044 2022-06-28T09:22:50 Z amunduzbaev One-Way Streets (CEOI17_oneway) C++17
100 / 100
 296 ms 41580 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] = (cmp[a[p]] == u);
		} else {
			is[p] = (cmp[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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12372 KB Output is correct
2 Correct 8 ms 12376 KB Output is correct
3 Correct 8 ms 12500 KB Output is correct
4 Correct 9 ms 12500 KB Output is correct
5 Correct 8 ms 12628 KB Output is correct
6 Correct 7 ms 12472 KB Output is correct
7 Correct 7 ms 12592 KB Output is correct
8 Correct 7 ms 12500 KB Output is correct
9 Correct 7 ms 12500 KB Output is correct
10 Correct 7 ms 12500 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12372 KB Output is correct
2 Correct 8 ms 12376 KB Output is correct
3 Correct 8 ms 12500 KB Output is correct
4 Correct 9 ms 12500 KB Output is correct
5 Correct 8 ms 12628 KB Output is correct
6 Correct 7 ms 12472 KB Output is correct
7 Correct 7 ms 12592 KB Output is correct
8 Correct 7 ms 12500 KB Output is correct
9 Correct 7 ms 12500 KB Output is correct
10 Correct 7 ms 12500 KB Output is correct
11 Correct 42 ms 17868 KB Output is correct
12 Correct 46 ms 18912 KB Output is correct
13 Correct 53 ms 20144 KB Output is correct
14 Correct 75 ms 21496 KB Output is correct
15 Correct 70 ms 21988 KB Output is correct
16 Correct 85 ms 22456 KB Output is correct
17 Correct 82 ms 25196 KB Output is correct
18 Correct 94 ms 22540 KB Output is correct
19 Correct 87 ms 28272 KB Output is correct
20 Correct 45 ms 18940 KB Output is correct
21 Correct 43 ms 18600 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12372 KB Output is correct
2 Correct 8 ms 12376 KB Output is correct
3 Correct 8 ms 12500 KB Output is correct
4 Correct 9 ms 12500 KB Output is correct
5 Correct 8 ms 12628 KB Output is correct
6 Correct 7 ms 12472 KB Output is correct
7 Correct 7 ms 12592 KB Output is correct
8 Correct 7 ms 12500 KB Output is correct
9 Correct 7 ms 12500 KB Output is correct
10 Correct 7 ms 12500 KB Output is correct
11 Correct 42 ms 17868 KB Output is correct
12 Correct 46 ms 18912 KB Output is correct
13 Correct 53 ms 20144 KB Output is correct
14 Correct 75 ms 21496 KB Output is correct
15 Correct 70 ms 21988 KB Output is correct
16 Correct 85 ms 22456 KB Output is correct
17 Correct 82 ms 25196 KB Output is correct
18 Correct 94 ms 22540 KB Output is correct
19 Correct 87 ms 28272 KB Output is correct
20 Correct 45 ms 18940 KB Output is correct
21 Correct 43 ms 18600 KB Output is correct
22 Correct 258 ms 38512 KB Output is correct
23 Correct 294 ms 36416 KB Output is correct
24 Correct 296 ms 32312 KB Output is correct
25 Correct 218 ms 41580 KB Output is correct
26 Correct 249 ms 35568 KB Output is correct
27 Correct 265 ms 34596 KB Output is correct
28 Correct 37 ms 16912 KB Output is correct
29 Correct 110 ms 22628 KB Output is correct
30 Correct 106 ms 22924 KB Output is correct
31 Correct 90 ms 22580 KB Output is correct
32 Correct 138 ms 28248 KB Output is correct