oj.uz

Submission #878649

# Submission time Handle Problem Language Result Execution time Memory
878649 2023-11-25T03:26:29 Z Jawad_Akbar_JJ One-Way Streets (CEOI17_oneway) C++14
60 / 100
 3000 ms 39764 KB 
#include <iostream>
#include <vector>
#include <map>

using namespace std;

const int N = 1e5  + 10;
vector<vector<int>> nei[N];
map<int,int> seen[N];
int ans[N];
int Seen[N];
int mn[N];
bool cyc[N];
int h[N];
int T = 1;
int inf = 1e9;
int target;
int U[N],V[N];






bool Dfs(int u){
	
	if (u==target)
		return true;
	if (Seen[u] == T)
		return false;
	
		
	Seen[u] = T;
	for (vector<int> v : nei[u]){
		int i = v[0];
		int t = v[1];
		int ind = v[2];
		
		if (Dfs(i)){
			ans[ind] |= t;
			return true;
		}
	}
	return false;
	
}





void dfs(int u,int p = -1,int hei = 1,int ind = 0){
	// cout<<"arrived at "<<u<<" "<<hei<<endl;
	mn[u] = inf;
	h[u] = hei;
	Seen[u] = T;
	for (vector<int> v : nei[u]){
		int i = v[0];
		if (i==p)
			continue;
		if (Seen[i] == T){
			cyc[v[2]] = true;
			// cout<<"have already Seen"<<i<<" "<<h[i]<<endl;
			mn[u] = min(mn[u],h[i]);
		}
		else{
			dfs(i,u,hei+1,v[2]);
			// cout<<"returned from "<<i<<" with mn "<<mn[i]<<endl;
			mn[u] = min(mn[u],mn[i]);
		}
	}
	if (mn[u]<hei)
		cyc[ind] = true;
}

signed main(){
	int n,m;
	cin>>n>>m;
	
	for (int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		U[i] = u;
		V[i] = v;
		seen[u][v]++;
		seen[v][u]++;
		if (seen[u][v]>1)
			continue;
		nei[u].push_back({v,1,i});
		nei[v].push_back({u,2,i});
	}
	
	int p;
	cin>>p;
	while (p--){
		int u;
		cin>>u>>target;
		T++;
		Dfs(u);
	}
	
	
	
	T++;
	
	for (int i=1;i<=n;i++)
		h[i] = inf;
	
	for (int i=1;i<=n;i++)
		if (Seen[i]!=T)
			dfs(i);
	
	for (int i=1;i<=m;i++)
		if (ans[i]%3==0 or cyc[i] or seen[U[i]][V[i]]>1)
			cout<<"B";
		else if (ans[i]==1)
			cout<<"R";
		else
			cout<<"L";
	cout<<endl;
			
	
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9560 KB Output is correct
2 Correct 2 ms 9564 KB Output is correct
3 Correct 3 ms 9820 KB Output is correct
4 Correct 3 ms 9820 KB Output is correct
5 Correct 6 ms 10024 KB Output is correct
6 Correct 3 ms 9820 KB Output is correct
7 Correct 4 ms 9820 KB Output is correct
8 Correct 4 ms 9820 KB Output is correct
9 Correct 5 ms 9820 KB Output is correct
10 Correct 6 ms 9820 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9560 KB Output is correct
2 Correct 2 ms 9564 KB Output is correct
3 Correct 3 ms 9820 KB Output is correct
4 Correct 3 ms 9820 KB Output is correct
5 Correct 6 ms 10024 KB Output is correct
6 Correct 3 ms 9820 KB Output is correct
7 Correct 4 ms 9820 KB Output is correct
8 Correct 4 ms 9820 KB Output is correct
9 Correct 5 ms 9820 KB Output is correct
10 Correct 6 ms 9820 KB Output is correct
11 Correct 341 ms 35920 KB Output is correct
12 Correct 465 ms 37376 KB Output is correct
13 Correct 885 ms 38744 KB Output is correct
14 Correct 1093 ms 38484 KB Output is correct
15 Correct 1055 ms 38340 KB Output is correct
16 Correct 237 ms 33248 KB Output is correct
17 Correct 865 ms 38228 KB Output is correct
18 Correct 562 ms 33244 KB Output is correct
19 Correct 1224 ms 39764 KB Output is correct
20 Correct 1080 ms 36436 KB Output is correct
21 Correct 897 ms 34692 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9560 KB Output is correct
2 Correct 2 ms 9564 KB Output is correct
3 Correct 3 ms 9820 KB Output is correct
4 Correct 3 ms 9820 KB Output is correct
5 Correct 6 ms 10024 KB Output is correct
6 Correct 3 ms 9820 KB Output is correct
7 Correct 4 ms 9820 KB Output is correct
8 Correct 4 ms 9820 KB Output is correct
9 Correct 5 ms 9820 KB Output is correct
10 Correct 6 ms 9820 KB Output is correct
11 Correct 341 ms 35920 KB Output is correct
12 Correct 465 ms 37376 KB Output is correct
13 Correct 885 ms 38744 KB Output is correct
14 Correct 1093 ms 38484 KB Output is correct
15 Correct 1055 ms 38340 KB Output is correct
16 Correct 237 ms 33248 KB Output is correct
17 Correct 865 ms 38228 KB Output is correct
18 Correct 562 ms 33244 KB Output is correct
19 Correct 1224 ms 39764 KB Output is correct
20 Correct 1080 ms 36436 KB Output is correct
21 Correct 897 ms 34692 KB Output is correct
22 Execution timed out 3037 ms 38424 KB Time limit exceeded
23 Halted 0 ms 0 KB -