oj.uz

답안 #873253

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
873253 2023-11-14T17:17:43 Z mdobric One-Way Streets (CEOI17_oneway) C++11
30 / 100
 95 ms 40336 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], be[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);
		}
	}
	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){
			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){
			be[x].push_back(make_pair(x_novi, in));
			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[1] = br1;
			br1++;
			parent[i] = i;
			dfs(i, 0, -1);
			brojac++;
		}
	}
	
	
	cin >> p;
	for (int i = 1; i <= p; i++){
		cin >> 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++;
		}
	}
	//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:46: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]
   46 |  for (int i = 0; i < v[x].size(); i++){
      |                  ~~^~~~~~~~~~~~~
oneway.cpp: In function 'void dfs2(int, int)':
oneway.cpp:72: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]
   72 |  for (int i = 0; i < e[x].size(); i++){
      |                  ~~^~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 15044 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 5 ms 15708 KB Output is correct
6 Correct 3 ms 14940 KB Output is correct
7 Correct 5 ms 15616 KB Output is correct
8 Correct 4 ms 15004 KB Output is correct
9 Correct 3 ms 15192 KB Output is correct
10 Correct 4 ms 15196 KB Output is correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 15044 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 5 ms 15708 KB Output is correct
6 Correct 3 ms 14940 KB Output is correct
7 Correct 5 ms 15616 KB Output is correct
8 Correct 4 ms 15004 KB Output is correct
9 Correct 3 ms 15192 KB Output is correct
10 Correct 4 ms 15196 KB Output is correct
11 Correct 39 ms 24916 KB Output is correct
12 Correct 50 ms 29264 KB Output is correct
13 Correct 76 ms 33924 KB Output is correct
14 Incorrect 95 ms 40336 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 15044 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 5 ms 15708 KB Output is correct
6 Correct 3 ms 14940 KB Output is correct
7 Correct 5 ms 15616 KB Output is correct
8 Correct 4 ms 15004 KB Output is correct
9 Correct 3 ms 15192 KB Output is correct
10 Correct 4 ms 15196 KB Output is correct
11 Correct 39 ms 24916 KB Output is correct
12 Correct 50 ms 29264 KB Output is correct
13 Correct 76 ms 33924 KB Output is correct
14 Incorrect 95 ms 40336 KB Output isn't correct
15 Halted 0 ms 0 KB -