oj.uz

Submission #463539

# Submission time Handle Problem Language Result Execution time Memory
463539 2021-08-11T09:52:47 Z vanic One-Way Streets (CEOI17_oneway) C++14
100 / 100
 111 ms 29664 KB 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstring>
#include <array>

using namespace std;

const int maxn=1e5+5;

struct union_find{
	int parent[maxn];
	int sz[maxn];
	union_find(){
		for(int i=0; i<maxn; i++){
			parent[i]=i;
			sz[i]=1;
		}
	}
	int find(int x){
		if(parent[x]==x){
			return x;
		}
		return parent[x]=find(parent[x]);
	}
	void update(int x, int y){
		x=find(x);
		y=find(y);
		if(sz[x]>sz[y]){
			swap(x, y);
		}
		parent[x]=y;
		sz[y]+=sz[x];
	}
	bool query(int x, int y){
		return find(x)==find(y);
	}
};


union_find U;
vector < array < int, 3 > > ms[maxn];
vector < array < int, 4 > > most;

int sol[maxn];
bool bio[maxn];
int disc[maxn];
int mini[maxn];

void dfs(int x, int prosl){
	bio[x]=1;
	if(prosl==x){
		disc[x]=0;
	}
	else{
		disc[x]=disc[prosl]+1;
	}
	bool p=0;
	mini[x]=disc[x];
	int y;
	for(int i=0; i<(int)ms[x].size(); i++){
		y=ms[x][i][0];
		if(!bio[y]){
			dfs(y, x);
			mini[x]=min(mini[x], mini[y]);
			if(disc[x]<mini[y]){
				most.push_back({x, y, ms[x][i][1], ms[x][i][2]});
			}
			else if(!U.query(x, y)){
				U.update(x, y);
			}
		}
		else{
			if(!p && y==prosl){
				p=1;
			}
			else{
				mini[x]=min(mini[x], disc[y]);
			}
		}
	}
}

vector < array < int, 3 > > novi[maxn];
int val[maxn];


int dfs1(int x, int prosl, int edge, bool p){
	int sum=val[x];
	bio[x]=1;
	for(int i=0; i<(int)novi[x].size(); i++){
		if(prosl!=novi[x][i][0]){
			sum+=dfs1(novi[x][i][0], x, novi[x][i][1], novi[x][i][2]^1);
		}
	}
	if(sum>0){
		if(p){
			sol[edge]=1;
		}
		else{
			sol[edge]=-1;
		}
	}
	else if(sum<0){
		if(p){
			sol[edge]=-1;
		}
		else{
			sol[edge]=1;
		}
	}
	return sum;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, m;
	cin >> n >> m;
	int a, b;
	for(int i=0; i<m; i++){
		cin >> a >> b;
		a--;
		b--;
		ms[a].push_back({b, i, 1});
		ms[b].push_back({a, i, 0});
	}
	for(int i=0; i<n; i++){
		if(!bio[i]){
			dfs(i, i);
		}
	}
/*	for(int i=0; i<(int)most.size(); i++){
		cout << most[i][0] << ' ' << most[i][1] << endl;
	}
	for(int i=0; i<n; i++){
		cout << disc[i] << ' ';
	}
	cout << endl;*/
	for(int i=0; i<(int)most.size(); i++){
		novi[U.find(most[i][0])].push_back({U.find(most[i][1]), most[i][2], most[i][3]});
		novi[U.find(most[i][1])].push_back({U.find(most[i][0]), most[i][2], most[i][3]^1});
	}
	int q;
	cin >> q;
	for(int i=0; i<q; i++){
		cin >> a >> b;
		a--;
		b--;
		a=U.find(a);
		b=U.find(b);
		val[a]++;
		val[b]--;
	}
	memset(bio, 0, sizeof(bio));
	for(int i=0; i<n; i++){
		if(!bio[U.find(i)]){
			dfs1(U.find(i), -1, m, 0);
		}
	}
	for(int i=0; i<m; i++){
		if(!sol[i]){
			cout << "B";
		}
		else if(sol[i]==1){
			cout << "R";
		}
		else{
			cout << "L";
		}
	}
	cout << '\n';
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5836 KB Output is correct
2 Correct 4 ms 5800 KB Output is correct
3 Correct 4 ms 5964 KB Output is correct
4 Correct 4 ms 5964 KB Output is correct
5 Correct 4 ms 6092 KB Output is correct
6 Correct 4 ms 5940 KB Output is correct
7 Correct 4 ms 6092 KB Output is correct
8 Correct 5 ms 5916 KB Output is correct
9 Correct 4 ms 5964 KB Output is correct
10 Correct 4 ms 5932 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5836 KB Output is correct
2 Correct 4 ms 5800 KB Output is correct
3 Correct 4 ms 5964 KB Output is correct
4 Correct 4 ms 5964 KB Output is correct
5 Correct 4 ms 6092 KB Output is correct
6 Correct 4 ms 5940 KB Output is correct
7 Correct 4 ms 6092 KB Output is correct
8 Correct 5 ms 5916 KB Output is correct
9 Correct 4 ms 5964 KB Output is correct
10 Correct 4 ms 5932 KB Output is correct
11 Correct 49 ms 13996 KB Output is correct
12 Correct 56 ms 15632 KB Output is correct
13 Correct 61 ms 17484 KB Output is correct
14 Correct 71 ms 18876 KB Output is correct
15 Correct 98 ms 19160 KB Output is correct
16 Correct 84 ms 18072 KB Output is correct
17 Correct 82 ms 22324 KB Output is correct
18 Correct 82 ms 18660 KB Output is correct
19 Correct 85 ms 24908 KB Output is correct
20 Correct 55 ms 14220 KB Output is correct
21 Correct 48 ms 14164 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5836 KB Output is correct
2 Correct 4 ms 5800 KB Output is correct
3 Correct 4 ms 5964 KB Output is correct
4 Correct 4 ms 5964 KB Output is correct
5 Correct 4 ms 6092 KB Output is correct
6 Correct 4 ms 5940 KB Output is correct
7 Correct 4 ms 6092 KB Output is correct
8 Correct 5 ms 5916 KB Output is correct
9 Correct 4 ms 5964 KB Output is correct
10 Correct 4 ms 5932 KB Output is correct
11 Correct 49 ms 13996 KB Output is correct
12 Correct 56 ms 15632 KB Output is correct
13 Correct 61 ms 17484 KB Output is correct
14 Correct 71 ms 18876 KB Output is correct
15 Correct 98 ms 19160 KB Output is correct
16 Correct 84 ms 18072 KB Output is correct
17 Correct 82 ms 22324 KB Output is correct
18 Correct 82 ms 18660 KB Output is correct
19 Correct 85 ms 24908 KB Output is correct
20 Correct 55 ms 14220 KB Output is correct
21 Correct 48 ms 14164 KB Output is correct
22 Correct 108 ms 22492 KB Output is correct
23 Correct 111 ms 18732 KB Output is correct
24 Correct 108 ms 18996 KB Output is correct
25 Correct 104 ms 29664 KB Output is correct
26 Correct 106 ms 21540 KB Output is correct
27 Correct 106 ms 18992 KB Output is correct
28 Correct 42 ms 10412 KB Output is correct
29 Correct 74 ms 13568 KB Output is correct
30 Correct 77 ms 14276 KB Output is correct
31 Correct 74 ms 14660 KB Output is correct
32 Correct 84 ms 20728 KB Output is correct