oj.uz

Submission #873339

# Submission time Handle Problem Language Result Execution time Memory
873339 2023-11-14T21:09:20 Z mdobric One-Way Streets (CEOI17_oneway) C++14
60 / 100
 3000 ms 31568 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, int> mp[100005];
map <int, int> :: 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(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);
		}
	}
	*/
	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:58: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]
   58 |  for (int i = 0; i < v[x].size(); i++){
      |                  ~~^~~~~~~~~~~~~
oneway.cpp: In function 'void dfs2(int, int)':
oneway.cpp:83: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]
   83 |  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 12888 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 4 ms 12888 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 4 ms 12892 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 3 ms 13032 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 4 ms 12888 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 4 ms 12892 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 3 ms 13032 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 30 ms 18268 KB Output is correct
12 Correct 40 ms 19656 KB Output is correct
13 Correct 47 ms 21076 KB Output is correct
14 Correct 70 ms 22212 KB Output is correct
15 Correct 70 ms 21844 KB Output is correct
16 Correct 41 ms 19320 KB Output is correct
17 Correct 85 ms 21840 KB Output is correct
18 Correct 45 ms 19284 KB Output is correct
19 Correct 82 ms 23472 KB Output is correct
20 Correct 47 ms 19392 KB Output is correct
21 Correct 42 ms 19024 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 4 ms 12888 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 4 ms 12892 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 3 ms 13032 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 30 ms 18268 KB Output is correct
12 Correct 40 ms 19656 KB Output is correct
13 Correct 47 ms 21076 KB Output is correct
14 Correct 70 ms 22212 KB Output is correct
15 Correct 70 ms 21844 KB Output is correct
16 Correct 41 ms 19320 KB Output is correct
17 Correct 85 ms 21840 KB Output is correct
18 Correct 45 ms 19284 KB Output is correct
19 Correct 82 ms 23472 KB Output is correct
20 Correct 47 ms 19392 KB Output is correct
21 Correct 42 ms 19024 KB Output is correct
22 Execution timed out 3034 ms 31568 KB Time limit exceeded
23 Halted 0 ms 0 KB -