oj.uz

Submission #873331

# Submission time Handle Problem Language Result Execution time Memory
873331 2023-11-14T20:34:50 Z mdobric One-Way Streets (CEOI17_oneway) C++14
30 / 100
 100 ms 40276 KB 
#include <bits/stdc++.h>
using namespace std;

int n, m, p;
int a[100005], b[100005], poc[100005], kraj[100005];
vector <pair <int, int> > v[100005];
vector <pair <int, int> > e[100005], be[100005];
int dt[100005], ft[100005], lw[100005];
int most[100005], blok[100005];
int brojac = 1;
int br1 = 1, br2 = 1;
int parent[100005];
int rez[100005];
map <int, int> mp[100005];

int find (int x){
	if (parent[x] == x){
		return x;
	}
	return parent[x] = find(parent[x]);
}

void unite (int x, int y){
	int px = find(x);
	int py = find(y);
	if (px == py){
		return;
	}
	if (mp[x].size() > mp[y].size()){
		swap(px, py);
	}
	for (auto i : mp[px]){
		mp[py][i.first]++;
		if (mp[py][i.first] == 2){
			mp[py].erase(i.first);
		}
	}
	parent[px] = py;
	return;
}

void dfs (int x, int p, int cesta){
	//cout << " aaa " << x << " " << p << endl;
	blok[x] = brojac;
	lw[x] = dt[x];
	for (int i = 0; i < v[x].size(); i++){
		int x_novi = v[x][i].first;
		int in = v[x][i].second;
		if (dt[x_novi] == 0 and cesta != in and x != x_novi){
			e[x].push_back(make_pair(x_novi, in));
			dt[x_novi] = br1;
			parent[x_novi] = x_novi;
			br1++;
			dfs(x_novi, x, in);
			lw[x] = min(lw[x], lw[x_novi]);
		}
		else
		if (cesta != in and x != x_novi){
			be[x].push_back(make_pair(x_novi, in));
			lw[x] = min(lw[x], dt[x_novi]);
		}
	}
	if (cesta != -1 and lw[x] == dt[x]){
		most[cesta] = 1;
	}
	ft[x] = br2;
	br2++;
	return;
}

void dfs2 (int x, int cesta){
	for (int i = 0; i < e[x].size(); i++){
		int x_novi = e[x][i].first;
		int in = e[x][i].second;
		dfs2(x_novi, in);
		unite(x, x_novi);
	}
	int px = find(x);
	if (cesta != -1 and mp[px].size() > 0){
		for (auto i : mp[px]){
			rez[cesta] = i.first;
			break;
		}
	}
	return;
}

int main (void){
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m;
	for (int i = 1; i <= m; i++){
		cin >> a[i] >> b[i];
		v[a[i]].push_back(make_pair(b[i], i));
		v[b[i]].push_back(make_pair(a[i], i));
	}
	for (int i = 1; i <= n; i++){
		if (blok[i] == 0){
			blok[i] = brojac;
			br1 = 1, br2 = 1;
			dt[i] = 1;
			br1++;
			parent[i] = i;
			dfs(i, 0, -1);
			brojac++;
		}
	}
	/*
	for (int i = 1; i <= n; i++){
		cout << blok[i] << endl;
		cout << i << " : ";
		for (int j = 0; j < e[i].size(); j++){
			cout << e[i][j].first << " ";
		}
		cout << endl;
	}
	*/
	cin >> p;
	for (int i = 1; i <= p; i++){
		cin >> poc[i] >> kraj[i];
		mp[poc[i]][i] = 1;
		mp[kraj[i]][i] = 1;
	}
	brojac = 1;
	for (int i = 1; i <= n; i++){
		if (blok[i] == brojac){
			dfs2(i, -1);
			brojac++;
		}
	}
	//cout << "aaa" << endl;
	//dfs2(1, -1);
	for (int i = 1; i <= m; i++){
		if (rez[i] == 0 or most[i] == 0){
			cout << "B";
		}
		else{
			int k = kraj[rez[i]];
			int p = poc[rez[i]];
			//cout << a[i] << " " << b[i] << " " << p << " " << k << endl;
			if ((dt[a[i]] < dt[b[i]] and dt[b[i]] <= dt[k] and ft[b[i]] >= ft[k]) or (dt[a[i]] > dt[b[i]] and dt[a[i]] <= dt[p] and ft[a[i]] >= ft[p])){
				cout << "R";
			}
			else{
				cout << "L";
			}
		}
	}
	
	return 0;
}

Compilation message

oneway.cpp: In function 'void dfs(int, int, int)':
oneway.cpp:46:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for (int i = 0; i < v[x].size(); i++){
      |                  ~~^~~~~~~~~~~~~
oneway.cpp: In function 'void dfs2(int, int)':
oneway.cpp:72:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  for (int i = 0; i < e[x].size(); i++){
      |                  ~~^~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 14956 KB Output is correct
4 Correct 4 ms 14940 KB Output is correct
5 Correct 5 ms 15960 KB Output is correct
6 Correct 3 ms 14944 KB Output is correct
7 Correct 4 ms 15544 KB Output is correct
8 Correct 3 ms 15196 KB Output is correct
9 Correct 3 ms 15196 KB Output is correct
10 Correct 3 ms 14996 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 14956 KB Output is correct
4 Correct 4 ms 14940 KB Output is correct
5 Correct 5 ms 15960 KB Output is correct
6 Correct 3 ms 14944 KB Output is correct
7 Correct 4 ms 15544 KB Output is correct
8 Correct 3 ms 15196 KB Output is correct
9 Correct 3 ms 15196 KB Output is correct
10 Correct 3 ms 14996 KB Output is correct
11 Correct 38 ms 25244 KB Output is correct
12 Correct 54 ms 29268 KB Output is correct
13 Correct 63 ms 34128 KB Output is correct
14 Incorrect 100 ms 40276 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 14956 KB Output is correct
4 Correct 4 ms 14940 KB Output is correct
5 Correct 5 ms 15960 KB Output is correct
6 Correct 3 ms 14944 KB Output is correct
7 Correct 4 ms 15544 KB Output is correct
8 Correct 3 ms 15196 KB Output is correct
9 Correct 3 ms 15196 KB Output is correct
10 Correct 3 ms 14996 KB Output is correct
11 Correct 38 ms 25244 KB Output is correct
12 Correct 54 ms 29268 KB Output is correct
13 Correct 63 ms 34128 KB Output is correct
14 Incorrect 100 ms 40276 KB Output isn't correct
15 Halted 0 ms 0 KB -