oj.uz

Submission #873343

# Submission time Handle Problem Language Result Execution time Memory
873343 2023-11-14T21:17:17 Z mdobric One-Way Streets (CEOI17_oneway) C++14
60 / 100
 623 ms 262144 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];
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, bool> mp[100005];
map <int, bool> :: iterator it;

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(parent[x]);
	int py = find(parent[y]);
	if (px == py){
		return;
	}
	if (mp[x].size() > mp[y].size()){
		swap(px, py);
	}
	
	for (auto i : mp[px]){
		if (mp[py][i.first] == 1){
			mp[py].erase(i.first);
		}
		else{
			mp[py][i.first] = 1;
		}
		
		
	}
	
	/*
	while (mp[px].size() > 0){
		//mp[px].begin();
		it = mp[px].begin();
		mp[py][it -> first]++;
		if (mp[py][it -> first] == 2){
			mp[py].erase(it -> first);
		}
		mp[px].erase(mp[px].begin());
	}
	*/
	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){
			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];
		if (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:64: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]
   64 |  for (int i = 0; i < v[x].size(); i++){
      |                  ~~^~~~~~~~~~~~~
oneway.cpp: In function 'void dfs2(int, int)':
oneway.cpp:89: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]
   89 |  for (int i = 0; i < e[x].size(); i++){
      |                  ~~^~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 5 ms 13752 KB Output is correct
6 Correct 3 ms 12904 KB Output is correct
7 Correct 4 ms 13404 KB Output is correct
8 Correct 3 ms 13148 KB Output is correct
9 Correct 3 ms 13148 KB Output is correct
10 Correct 3 ms 12888 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 5 ms 13752 KB Output is correct
6 Correct 3 ms 12904 KB Output is correct
7 Correct 4 ms 13404 KB Output is correct
8 Correct 3 ms 13148 KB Output is correct
9 Correct 3 ms 13148 KB Output is correct
10 Correct 3 ms 12888 KB Output is correct
11 Correct 35 ms 19796 KB Output is correct
12 Correct 48 ms 24148 KB Output is correct
13 Correct 62 ms 29272 KB Output is correct
14 Correct 77 ms 36068 KB Output is correct
15 Correct 77 ms 33164 KB Output is correct
16 Correct 50 ms 19540 KB Output is correct
17 Correct 111 ms 49744 KB Output is correct
18 Correct 42 ms 19792 KB Output is correct
19 Correct 110 ms 49528 KB Output is correct
20 Correct 58 ms 30548 KB Output is correct
21 Correct 51 ms 25680 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 5 ms 13752 KB Output is correct
6 Correct 3 ms 12904 KB Output is correct
7 Correct 4 ms 13404 KB Output is correct
8 Correct 3 ms 13148 KB Output is correct
9 Correct 3 ms 13148 KB Output is correct
10 Correct 3 ms 12888 KB Output is correct
11 Correct 35 ms 19796 KB Output is correct
12 Correct 48 ms 24148 KB Output is correct
13 Correct 62 ms 29272 KB Output is correct
14 Correct 77 ms 36068 KB Output is correct
15 Correct 77 ms 33164 KB Output is correct
16 Correct 50 ms 19540 KB Output is correct
17 Correct 111 ms 49744 KB Output is correct
18 Correct 42 ms 19792 KB Output is correct
19 Correct 110 ms 49528 KB Output is correct
20 Correct 58 ms 30548 KB Output is correct
21 Correct 51 ms 25680 KB Output is correct
22 Runtime error 623 ms 262144 KB Execution killed with signal 9
23 Halted 0 ms 0 KB -