oj.uz

Submission #873336

# Submission time Handle Problem Language Result Execution time Memory
873336 2023-11-14T21:01:18 Z mdobric One-Way Streets (CEOI17_oneway) C++14
60 / 100
 3000 ms 35160 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];

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].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:49: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]
   49 |  for (int i = 0; i < v[x].size(); i++){
      |                  ~~^~~~~~~~~~~~~
oneway.cpp: In function 'void dfs2(int, int)':
oneway.cpp:74: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]
   74 |  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 3 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 4 ms 12888 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 3 ms 13080 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 3 ms 12892 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 12892 KB Output is correct
2 Correct 3 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 4 ms 12888 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 3 ms 13080 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 3 ms 12892 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 37 ms 18424 KB Output is correct
12 Correct 40 ms 19680 KB Output is correct
13 Correct 49 ms 21048 KB Output is correct
14 Correct 74 ms 21840 KB Output is correct
15 Correct 60 ms 21876 KB Output is correct
16 Correct 59 ms 19328 KB Output is correct
17 Correct 100 ms 22148 KB Output is correct
18 Correct 42 ms 19292 KB Output is correct
19 Correct 82 ms 23476 KB Output is correct
20 Correct 48 ms 19540 KB Output is correct
21 Correct 44 ms 19036 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 3 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 4 ms 12888 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 3 ms 13080 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 3 ms 12892 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 37 ms 18424 KB Output is correct
12 Correct 40 ms 19680 KB Output is correct
13 Correct 49 ms 21048 KB Output is correct
14 Correct 74 ms 21840 KB Output is correct
15 Correct 60 ms 21876 KB Output is correct
16 Correct 59 ms 19328 KB Output is correct
17 Correct 100 ms 22148 KB Output is correct
18 Correct 42 ms 19292 KB Output is correct
19 Correct 82 ms 23476 KB Output is correct
20 Correct 48 ms 19540 KB Output is correct
21 Correct 44 ms 19036 KB Output is correct
22 Execution timed out 3063 ms 35160 KB Time limit exceeded
23 Halted 0 ms 0 KB -