oj.uz

답안 #873334

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
873334 2023-11-14T20:52:47 Z mdobric One-Way Streets (CEOI17_oneway) C++14
60 / 100
 652 ms 262144 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 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){
			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[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: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 4 ms 14936 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 14936 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 5 ms 15708 KB Output is correct
6 Correct 4 ms 14940 KB Output is correct
7 Correct 4 ms 15452 KB Output is correct
8 Correct 4 ms 15196 KB Output is correct
9 Correct 3 ms 15196 KB Output is correct
10 Correct 4 ms 15096 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 14936 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 14936 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 5 ms 15708 KB Output is correct
6 Correct 4 ms 14940 KB Output is correct
7 Correct 4 ms 15452 KB Output is correct
8 Correct 4 ms 15196 KB Output is correct
9 Correct 3 ms 15196 KB Output is correct
10 Correct 4 ms 15096 KB Output is correct
11 Correct 38 ms 23888 KB Output is correct
12 Correct 50 ms 28044 KB Output is correct
13 Correct 69 ms 32912 KB Output is correct
14 Correct 89 ms 39252 KB Output is correct
15 Correct 80 ms 37200 KB Output is correct
16 Correct 43 ms 22864 KB Output is correct
17 Correct 134 ms 53128 KB Output is correct
18 Correct 58 ms 22868 KB Output is correct
19 Correct 113 ms 52596 KB Output is correct
20 Correct 67 ms 35776 KB Output is correct
21 Correct 63 ms 30548 KB Output is correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 14936 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 14936 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 5 ms 15708 KB Output is correct
6 Correct 4 ms 14940 KB Output is correct
7 Correct 4 ms 15452 KB Output is correct
8 Correct 4 ms 15196 KB Output is correct
9 Correct 3 ms 15196 KB Output is correct
10 Correct 4 ms 15096 KB Output is correct
11 Correct 38 ms 23888 KB Output is correct
12 Correct 50 ms 28044 KB Output is correct
13 Correct 69 ms 32912 KB Output is correct
14 Correct 89 ms 39252 KB Output is correct
15 Correct 80 ms 37200 KB Output is correct
16 Correct 43 ms 22864 KB Output is correct
17 Correct 134 ms 53128 KB Output is correct
18 Correct 58 ms 22868 KB Output is correct
19 Correct 113 ms 52596 KB Output is correct
20 Correct 67 ms 35776 KB Output is correct
21 Correct 63 ms 30548 KB Output is correct
22 Runtime error 652 ms 262144 KB Execution killed with signal 9
23 Halted 0 ms 0 KB -