oj.uz

Submission #873754

# Submission time Handle Problem Language Result Execution time Memory
873754 2023-11-15T15:54:55 Z mdobric One-Way Streets (CEOI17_oneway) C++14
100 / 100
 116 ms 32332 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], d[100005];
int brojac = 1;
int br1 = 1, br2 = 1;
int parent[100005], par[100005];
int rez[100005], ans[100005], max_lca[100005];
int go[100005][17];

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;
	}
	//cout << x << " " << y << endl;
	//cout << px << " " << py << endl;
	if (x == max_lca[px] or y == max_lca[px]){
		//cout << "aaa" << endl;
		ans[px] = 0;
		max_lca[px] = 0;
	}
	if (x == max_lca[py] or y == max_lca[py]){
		//cout << "bbb" << endl;
		ans[py] = 0;
		max_lca[py] = 0;
	}
	
	if (ans[px] != 0 and (d[max_lca[px]] < d[max_lca[py]] or ans[py] == 0)){
		parent[py] = px;
		//cout << ans[px] << endl << endl;
	}
	else{
		parent[px] = py;
		//cout << ans[py] << endl << endl;
	}
	/*
	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;
			par[x_novi] = x;
			br1++;
			d[x_novi] = d[x] + 1;
			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){
		rez[cesta] = ans[px];
	}
	return;
}

int idi (int x, int i){
	//cout << x << " " << i << endl;
	if (go[x][i] != -1){
		return go[x][i];
	}
	if (i == 0){
		go[x][i] = par[x];
		return go[x][i];
	}
	int pola = idi(x, i - 1);
	go[x][i] = idi(pola, i - 1);
	return go[x][i];
}

int lca (int x, int y){
	if (blok[x] != blok[y]){
		return 0;
	}
	if (d[x] < d[y]){
		swap(x, y);
	}
	//cout << " aaa " << x << " " << y << endl;
	for (int i = 16; i >= 0; i--){
		int novi_x = idi(x, i);
		if (d[novi_x] >= d[y]){
			x = novi_x;
		}
	}
	//cout << " bbb " << x << " " << y << endl;
	if (x == y){
		return x;
	}
	for (int i = 16; i >= 0; i--){
		int novi_x = idi(x, i);
		int novi_y = idi(y, i);
		if (novi_x != novi_y){
			x = novi_x;
			y = novi_y;
		}
	}
	return par[x];
}

int main (void){
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	memset(go, -1, sizeof go);
	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){
			d[i] = 1;
			blok[i] = brojac;
			br1 = 1, br2 = 1;
			dt[i] = 1;
			br1++;
			parent[i] = i;
			par[i] = i;
			dfs(i, 0, -1);
			brojac++;
		}
	}
	/*
	for (int i = 1; i <= n; i++){
		//cout << blok[i] << endl;
		for (int j = 0; j < e[i].size(); j++){
			cout << i << " " << e[i][j].first << endl;
		}
		cout << endl;
	}
	*/
	//cout << d[7] << d[2] << endl;
	p = unos();
	for (int i = 1; i <= p; i++){
		poc[i] = unos();
		kraj[i] = unos();
		int lca_tr = lca(poc[i], kraj[i]);
		//cout << lca_tr << endl;
		if (poc[i] != kraj[i]){
			if (max_lca[poc[i]] == 0 or d[lca_tr] < d[max_lca[poc[i]]]){
				max_lca[poc[i]] = lca_tr;
				ans[poc[i]] = i;
			}
			if (max_lca[kraj[i]] == 0 or d[lca_tr] < d[max_lca[kraj[i]]]){
				max_lca[kraj[i]] = lca_tr;
				ans[kraj[i]] = i;
			}
		}
		
	}
	/*
	for (int i = 1; i <= n; i++){
		cout << i << "  " << ans[i] << endl;
	}
	*/
	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:81:2: warning: "/*" within comment [-Wcomment]
   81 |  /*
      |   
oneway.cpp: In function 'void dfs(int, int, int)':
oneway.cpp:100: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]
  100 |  for (int i = 0; i < v[x].size(); i++){
      |                  ~~^~~~~~~~~~~~~
oneway.cpp: In function 'void dfs2(int, int)':
oneway.cpp:127: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]
  127 |  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 14940 KB Output is correct
2 Correct 2 ms 14808 KB Output is correct
3 Correct 3 ms 15132 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 4 ms 14936 KB Output is correct
7 Correct 3 ms 14940 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 3 ms 15116 KB Output is correct
10 Correct 3 ms 15068 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14940 KB Output is correct
2 Correct 2 ms 14808 KB Output is correct
3 Correct 3 ms 15132 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 4 ms 14936 KB Output is correct
7 Correct 3 ms 14940 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 3 ms 15116 KB Output is correct
10 Correct 3 ms 15068 KB Output is correct
11 Correct 22 ms 20572 KB Output is correct
12 Correct 27 ms 22364 KB Output is correct
13 Correct 36 ms 24176 KB Output is correct
14 Correct 41 ms 25424 KB Output is correct
15 Correct 53 ms 25848 KB Output is correct
16 Correct 42 ms 23348 KB Output is correct
17 Correct 44 ms 25936 KB Output is correct
18 Correct 33 ms 23380 KB Output is correct
19 Correct 44 ms 27408 KB Output is correct
20 Correct 28 ms 22108 KB Output is correct
21 Correct 28 ms 22280 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14940 KB Output is correct
2 Correct 2 ms 14808 KB Output is correct
3 Correct 3 ms 15132 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 4 ms 14936 KB Output is correct
7 Correct 3 ms 14940 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 3 ms 15116 KB Output is correct
10 Correct 3 ms 15068 KB Output is correct
11 Correct 22 ms 20572 KB Output is correct
12 Correct 27 ms 22364 KB Output is correct
13 Correct 36 ms 24176 KB Output is correct
14 Correct 41 ms 25424 KB Output is correct
15 Correct 53 ms 25848 KB Output is correct
16 Correct 42 ms 23348 KB Output is correct
17 Correct 44 ms 25936 KB Output is correct
18 Correct 33 ms 23380 KB Output is correct
19 Correct 44 ms 27408 KB Output is correct
20 Correct 28 ms 22108 KB Output is correct
21 Correct 28 ms 22280 KB Output is correct
22 Correct 116 ms 25688 KB Output is correct
23 Correct 93 ms 25684 KB Output is correct
24 Correct 84 ms 25744 KB Output is correct
25 Correct 114 ms 32332 KB Output is correct
26 Correct 104 ms 27472 KB Output is correct
27 Correct 99 ms 25912 KB Output is correct
28 Correct 19 ms 18780 KB Output is correct
29 Correct 79 ms 23936 KB Output is correct
30 Correct 75 ms 24144 KB Output is correct
31 Correct 76 ms 24524 KB Output is correct
32 Correct 85 ms 28000 KB Output is correct