oj.uz

Submission #938386

# Submission time Handle Problem Language Result Execution time Memory
938386 2024-03-05T05:33:16 Z vjudge1 One-Way Streets (CEOI17_oneway) C++17
60 / 100
 3000 ms 65660 KB 
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pb push_back
#define fr first
#define sc second
const long long INF=1e17,N=2e5+6;
vector<int> ar[N],up(N),tin(N),color(N);
vector<bool> used(N);
int timer,mxcol=0;
map<pair<int,int>,bool> mp;
map<pair<int,int>,int> e_cnt;
void bridge(int x, int p=-1){
	used[x]=1;
	tin[x]=up[x]=timer++;
	for(auto it: ar[x]){
		if(it==p) continue;
		if(used[it])
			up[x]=min(up[x],tin[it]);
		else{
			bridge(it,x);
			up[x]=min(up[x],up[it]);
			if(up[it]>tin[x]){
				mp[{it,x}]=1;
				mp[{x,it}]=1;
			}
		}
	}
}
void dfs(int x, int c){
	color[x]=c;
	used[x]=1;
	for(auto it: ar[x]){
		if(!used[it] && (!mp[{x,it}] || e_cnt[{x,it}]!=1))
			dfs(it,c);
	}
}

int n,m;
int ans[N],A[N],B[N];
map<pair<int,int>,int> edge;
vector<pair<int,int>> g[N];
int k;
int vis[N];
int DFS(int x, int f){
	if(x==f) return 1;
	vis[x]=1;
	bool res=0;
	for(auto it: g[x]){
		if(vis[it.fr]) continue;
		if(DFS(it.fr,f)){
			int t=it.sc;
			if(t<0)
				ans[-t]=0;
			else
				ans[t]=1;
			res=1;
		}
	}
	vis[x]=0;
	return res;
}
int c=0;
void get(){
	cin>>k;
	for(int i=0;i<k;i++){
		int a,b;cin>>a>>b;a--,b--;
		DFS(color[a],color[b]);
	}
	for(int i=1;i<=m;i++){
		if(ans[i]==2) cout<<'B';
		else if(ans[i]==1) cout<<'R';
		else cout<<'L';
	}
}
void solve(){
	cin>>n>>m;
	vector<pair<int,int>> e;
	for(int i=0;i<m;i++){
		ans[i+1]=2;
		int a,b;
		cin>>a>>b;
		a--;
		b--;
		e_cnt[{a,b}]++;
		e_cnt[{b,a}]++;
		ar[a].pb(b);
		ar[b].pb(a);
		edge[{a,b}]=i+1;
		edge[{b,a}]=-i-1;
		e.pb({a,b});
	}
	for(int i=0;i<n;i++){
		if(!used[i])
			bridge(i);
	}
	used.assign(N,0);
	
	for(int i=0;i<n;i++){
		if(!used[i])
			dfs(i,++c);
	}	
	for(auto it: e){
		if(color[it.fr]!=color[it.sc]){
			g[color[it.fr]].pb({color[it.sc],edge[it]});
			g[color[it.sc]].pb({color[it.fr],edge[{it.sc,it.fr}]});
		}
	}
	get();
}
main(){
	int T=1;
	//cin>>T;
	while(T--){
		solve();
	}
}

Compilation message

oneway.cpp:111:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  111 | main(){
      | ^~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15192 KB Output is correct
2 Correct 4 ms 15196 KB Output is correct
3 Correct 5 ms 15448 KB Output is correct
4 Correct 5 ms 15544 KB Output is correct
5 Correct 6 ms 15452 KB Output is correct
6 Correct 4 ms 15196 KB Output is correct
7 Correct 6 ms 15684 KB Output is correct
8 Correct 6 ms 15448 KB Output is correct
9 Correct 5 ms 15452 KB Output is correct
10 Correct 5 ms 15460 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15192 KB Output is correct
2 Correct 4 ms 15196 KB Output is correct
3 Correct 5 ms 15448 KB Output is correct
4 Correct 5 ms 15544 KB Output is correct
5 Correct 6 ms 15452 KB Output is correct
6 Correct 4 ms 15196 KB Output is correct
7 Correct 6 ms 15684 KB Output is correct
8 Correct 6 ms 15448 KB Output is correct
9 Correct 5 ms 15452 KB Output is correct
10 Correct 5 ms 15460 KB Output is correct
11 Correct 269 ms 46568 KB Output is correct
12 Correct 296 ms 48320 KB Output is correct
13 Correct 323 ms 50852 KB Output is correct
14 Correct 373 ms 54672 KB Output is correct
15 Correct 412 ms 55976 KB Output is correct
16 Correct 528 ms 61976 KB Output is correct
17 Correct 643 ms 64708 KB Output is correct
18 Correct 726 ms 61828 KB Output is correct
19 Correct 634 ms 65660 KB Output is correct
20 Correct 256 ms 48836 KB Output is correct
21 Correct 223 ms 47488 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15192 KB Output is correct
2 Correct 4 ms 15196 KB Output is correct
3 Correct 5 ms 15448 KB Output is correct
4 Correct 5 ms 15544 KB Output is correct
5 Correct 6 ms 15452 KB Output is correct
6 Correct 4 ms 15196 KB Output is correct
7 Correct 6 ms 15684 KB Output is correct
8 Correct 6 ms 15448 KB Output is correct
9 Correct 5 ms 15452 KB Output is correct
10 Correct 5 ms 15460 KB Output is correct
11 Correct 269 ms 46568 KB Output is correct
12 Correct 296 ms 48320 KB Output is correct
13 Correct 323 ms 50852 KB Output is correct
14 Correct 373 ms 54672 KB Output is correct
15 Correct 412 ms 55976 KB Output is correct
16 Correct 528 ms 61976 KB Output is correct
17 Correct 643 ms 64708 KB Output is correct
18 Correct 726 ms 61828 KB Output is correct
19 Correct 634 ms 65660 KB Output is correct
20 Correct 256 ms 48836 KB Output is correct
21 Correct 223 ms 47488 KB Output is correct
22 Execution timed out 3055 ms 64504 KB Time limit exceeded
23 Halted 0 ms 0 KB -