oj.uz

Submission #941893

# Submission time Handle Problem Language Result Execution time Memory
941893 2024-03-09T16:12:48 Z vjudge1 One-Way Streets (CEOI17_oneway) C++17
100 / 100
 580 ms 86220 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pii pair<int,int>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define f first
#define int long long
#define s second
#define pii pair<int,int>
template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}
typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
	tree_order_statistics_node_update> ordered_set;
const int N=3e5 + 5	;
const int inf = 1e17 + 7;
const int mod = 998244353;
 
map<pii,int>e_cnt,edge,mp;
 
vector<int>g[N],vis(N),tin(N),fup(N),color(N),A(N),B(N),ans(N);
 
vector<pii>v[N],nw;
 
int n,m,k, timer;
 
 
void bridge(int x, int p = -1){
 
	vis[x] = 1;
	tin[x] = ++timer;
	fup[x] = ++timer;
	
	for(auto to:g[x]){
		if(to == p)continue;
		if(vis[to]){
			 umin(fup[x],fup[to]);
		}
		else{
			bridge(to,x);
			umin(fup[x],fup[to]);
			if(fup[to]>tin[x]){
				mp[{x,to}] = 1;
				mp[{to,x}] = 1;
			}
		}
	}
}
 
void dfs(int x, int col){
	
	vis[x] = 1;
	color[x] = col;
	
	for(auto to:g[x]){
		if(vis[to])continue;
		
		if(mp[{x,to}] != 1 || e_cnt[{to,x}] > 1)
			dfs(to,col);
	}
}
 
void DFS(int x, int p){
	vis[x] = 1;
	for(auto [to,ind]:v[x]){
		if(to == p)continue;
		DFS(to,x);
		A[x] += A[to];
		B[x] += B[to];
	}
	
	for(auto [to,ind]:v[x]){
		if(to == p) continue;
		if(A[to] != B[to]){
			
			if(ind < 0)
				ans[-ind]=1;
			else
				ans[ind]=0;
			if(B[to]>A[to]) ans[abs(ind )]^=1;
		}
	}
	
}
int c = 1;
void magic_nahuy(){
	
	int op;cin >> op;
	for(int i = 1;i<=m;i++){
		ans[i] = 2;
	}
	
	for(int i = 1;i<=n;i++){
		vis[i] = 0;
	}
	
	for(int i = 0;i<op;i++){
		int a,b;
		cin >> a >> b;
		A[color[a]] += 1;
		B[color[b]] += 1;
	}
	
	
	for(int i = 1;i<=c;i++){
		if(vis[i])continue;
			DFS(i,-1);
	}
	
	for(int i = 1;i<=m;i++){
		if(ans[i] == 2)cout<<"B";
		if(ans[i] == 1)cout<<"R";
		if(ans[i] == 0)cout<<"L";
		
		
	}
	
}
 
void solve(){
	
	cin >> n >> m;
	
	for(int i = 1; i<=m ;i++){
		int a,b;
		cin >> a >> b;
		
		e_cnt[{a,b}] += 1;
		e_cnt[{b,a}] += 1;
		
		g[a].pb(b);
		g[b].pb(a);
		
		edge[{a,b}] = i;
		edge[{b,a}] = -i;
		
		nw.pb({a,b});
	}
	
	
	
	for(int i = 1;i<=n;i++){
		if(vis[i])continue;
			bridge(i);
	}
	
	for(int i = 1;i<=n;i++){
		vis[i] = 0;
	}
	
	
	for(int i = 1;i<=n;i++){
		if(vis[i])continue;
			dfs(i,c++);
		
	}
	
	for(auto it:nw){
		if(color[it.f] == color[it.s])continue;
		
		v[color[it.f]].pb({color[it.s],edge[it]});
		v[color[it.s]].pb({color[it.f],-edge[it]});
	}
	
	magic_nahuy();
	
}
 
signed main()
{
//	freopen("seq.in", "r", stdin);
//  freopen("seq.out", "w", stdout);
	ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
	int tt=1;//cin>>tt>>n;
	while(tt--)solve();
 
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 30808 KB Output is correct
2 Correct 9 ms 30812 KB Output is correct
3 Correct 10 ms 31368 KB Output is correct
4 Correct 11 ms 31476 KB Output is correct
5 Correct 13 ms 31320 KB Output is correct
6 Correct 10 ms 31068 KB Output is correct
7 Correct 11 ms 31324 KB Output is correct
8 Correct 11 ms 31324 KB Output is correct
9 Correct 10 ms 31212 KB Output is correct
10 Correct 12 ms 31064 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 30808 KB Output is correct
2 Correct 9 ms 30812 KB Output is correct
3 Correct 10 ms 31368 KB Output is correct
4 Correct 11 ms 31476 KB Output is correct
5 Correct 13 ms 31320 KB Output is correct
6 Correct 10 ms 31068 KB Output is correct
7 Correct 11 ms 31324 KB Output is correct
8 Correct 11 ms 31324 KB Output is correct
9 Correct 10 ms 31212 KB Output is correct
10 Correct 12 ms 31064 KB Output is correct
11 Correct 253 ms 63824 KB Output is correct
12 Correct 276 ms 65848 KB Output is correct
13 Correct 283 ms 68280 KB Output is correct
14 Correct 339 ms 71876 KB Output is correct
15 Correct 357 ms 73144 KB Output is correct
16 Correct 534 ms 79116 KB Output is correct
17 Correct 407 ms 81340 KB Output is correct
18 Correct 487 ms 79056 KB Output is correct
19 Correct 404 ms 83136 KB Output is correct
20 Correct 241 ms 65480 KB Output is correct
21 Correct 234 ms 64024 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 30808 KB Output is correct
2 Correct 9 ms 30812 KB Output is correct
3 Correct 10 ms 31368 KB Output is correct
4 Correct 11 ms 31476 KB Output is correct
5 Correct 13 ms 31320 KB Output is correct
6 Correct 10 ms 31068 KB Output is correct
7 Correct 11 ms 31324 KB Output is correct
8 Correct 11 ms 31324 KB Output is correct
9 Correct 10 ms 31212 KB Output is correct
10 Correct 12 ms 31064 KB Output is correct
11 Correct 253 ms 63824 KB Output is correct
12 Correct 276 ms 65848 KB Output is correct
13 Correct 283 ms 68280 KB Output is correct
14 Correct 339 ms 71876 KB Output is correct
15 Correct 357 ms 73144 KB Output is correct
16 Correct 534 ms 79116 KB Output is correct
17 Correct 407 ms 81340 KB Output is correct
18 Correct 487 ms 79056 KB Output is correct
19 Correct 404 ms 83136 KB Output is correct
20 Correct 241 ms 65480 KB Output is correct
21 Correct 234 ms 64024 KB Output is correct
22 Correct 441 ms 81488 KB Output is correct
23 Correct 460 ms 78792 KB Output is correct
24 Correct 580 ms 78960 KB Output is correct
25 Correct 417 ms 86220 KB Output is correct
26 Correct 423 ms 80880 KB Output is correct
27 Correct 492 ms 79220 KB Output is correct
28 Correct 80 ms 36036 KB Output is correct
29 Correct 251 ms 64916 KB Output is correct
30 Correct 237 ms 64964 KB Output is correct
31 Correct 259 ms 65936 KB Output is correct
32 Correct 274 ms 67716 KB Output is correct