oj.uz

Submission #873733

# Submission time Handle Problem Language Result Execution time Memory
873733 2023-11-15T14:40:07 Z mdobric One-Way Streets (CEOI17_oneway) C++14
60 / 100
 3000 ms 33892 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;

bool isbroj(char x) {
	return x >= '0' && x <= '9';
}

long long unos() {
	long long res = 0;
	char ch;
	while (!isbroj(ch = getchar()));
	res = ch - '0';
	while (isbroj(ch = getchar())) {
		res = res * 10 + ch - '0';
	}
	return res;
}

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;
		}	
	}
	mp[px].clear();
	
	/*
	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);
	n = unos();
	m = unos();
	for (int i = 1; i <= m; i++){
		a[i] = unos();
		b[i] = unos();
		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;
	}
	*/
	p = unos();
	for (int i = 1; i <= p; i++){
		poc[i] = unos();
		kraj[i] = unos();
		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";
			}
		}
	}
	cout << "\n";
	
	return 0;
}

Compilation message

oneway.cpp: In function 'void dfs(int, int, int)':
oneway.cpp:78: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]
   78 |  for (int i = 0; i < v[x].size(); i++){
      |                  ~~^~~~~~~~~~~~~
oneway.cpp: In function 'void dfs2(int, int)':
oneway.cpp:103: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]
  103 |  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 12892 KB Output is correct
2 Correct 3 ms 12952 KB Output is correct
3 Correct 3 ms 13144 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 4 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 3 ms 12896 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 3 ms 12892 KB Output is correct
10 Correct 2 ms 13144 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 3 ms 12952 KB Output is correct
3 Correct 3 ms 13144 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 4 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 3 ms 12896 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 3 ms 12892 KB Output is correct
10 Correct 2 ms 13144 KB Output is correct
11 Correct 25 ms 19036 KB Output is correct
12 Correct 39 ms 20460 KB Output is correct
13 Correct 43 ms 21796 KB Output is correct
14 Correct 58 ms 22620 KB Output is correct
15 Correct 58 ms 22616 KB Output is correct
16 Correct 34 ms 20056 KB Output is correct
17 Correct 69 ms 22620 KB Output is correct
18 Correct 44 ms 20056 KB Output is correct
19 Correct 73 ms 24156 KB Output is correct
20 Correct 42 ms 20304 KB Output is correct
21 Correct 34 ms 19884 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 3 ms 12952 KB Output is correct
3 Correct 3 ms 13144 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 4 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 3 ms 12896 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 3 ms 12892 KB Output is correct
10 Correct 2 ms 13144 KB Output is correct
11 Correct 25 ms 19036 KB Output is correct
12 Correct 39 ms 20460 KB Output is correct
13 Correct 43 ms 21796 KB Output is correct
14 Correct 58 ms 22620 KB Output is correct
15 Correct 58 ms 22616 KB Output is correct
16 Correct 34 ms 20056 KB Output is correct
17 Correct 69 ms 22620 KB Output is correct
18 Correct 44 ms 20056 KB Output is correct
19 Correct 73 ms 24156 KB Output is correct
20 Correct 42 ms 20304 KB Output is correct
21 Correct 34 ms 19884 KB Output is correct
22 Execution timed out 3039 ms 33892 KB Time limit exceeded
23 Halted 0 ms 0 KB -