oj.uz

Submission #535446

# Submission time Handle Problem Language Result Execution time Memory
535446 2022-03-10T09:29:51 Z Asymmetry One-Way Streets (CEOI17_oneway) C++17
100 / 100
 118 ms 21412 KB 
//Autor: Bartłomiej Czarkowski
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n'
#else
#define debug(...) {}
#endif

const int N = 101000;
int n, m, q, a, b, l;
int dp[N];
int kr[N][2];
int sss[N];
int odw[N];
int gle[N];
int odp[N];
int stp[N];
int pd[N];
vector<int> v[N];
vector<pair<int, int>> vv[N];

void dfs_gle(int x) {
	odw[x] = l;
	for (int i : v[x]) {
		if (odw[i] < l) {
			gle[i] = gle[x] + 1;
			dfs_gle(i);
		}
	}
}

void dfs_dp(int x) {
	odw[x] = l;
	for (int i : v[x]) {
		if (odw[i] < l) {
			dfs_dp(i);
			dp[x] += dp[i];
		}
	}
}

void dfs_sss(int x) {
	odw[x] = l;
	for (int i : v[x]) {
		if (odw[i] < l) {
			if (dp[i] > 1) {
				sss[i] = sss[x];
			}
			dfs_sss(i);
		}
	}
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; ++i) {
		scanf("%d%d", &a, &b);
		v[a].push_back(b);
		v[b].push_back(a);
		kr[i][0] = a;
		kr[i][1] = b;
	}
	++l;
	for (int i = 1; i <= n; ++i) {
		if (odw[i] < l) {
			dfs_gle(i);
		}
	}
	for (int i = 1; i <= m; ++i) {
		if (gle[kr[i][0]] > gle[kr[i][1]]) {
			odp[i] = 1;
			swap(kr[i][0], kr[i][1]);
		}
		++dp[kr[i][1]];
		--dp[kr[i][0]];
	}
	++l;
	for (int i = 1; i <= n; ++i) {
		if (odw[i] < l) {
			dfs_dp(i);
		}
		sss[i] = i;
	}
	++l;
	for (int i = 1; i <= n; ++i) {
		if (odw[i] < l) {
			dfs_sss(i);
		}
	}
	//~ for (int i = 1; i <= n; ++i) {
		//~ printf("%d ", sss[i]);
	//~ }
	//~ printf("\n");
	for (int i = 1; i <= m; ++i) {
		if (sss[kr[i][0]] == sss[kr[i][1]]) {
			odp[i] = 2;
		}
		else {
			vv[sss[kr[i][0]]].push_back({sss[kr[i][1]], i});
			vv[sss[kr[i][1]]].push_back({sss[kr[i][0]], i});
			++stp[sss[kr[i][0]]];
			++stp[sss[kr[i][1]]];
		}
	}
	scanf("%d", &q);
	for (int i = 1; i <= q; ++i) {
		scanf("%d%d", &a, &b);
		++pd[sss[a]];
		--pd[sss[b]];
	}
	queue<int> que;
	for (int i = 1; i <= n; ++i) {
		if (stp[i] == 1) {
			que.push(i);
		}
	}
	++l;
	while (!que.empty()) {
		int x = que.front();
		que.pop();
		odw[x] = l;
		for (auto i : vv[x]) {
			if (odw[i.first] < l) {
				--stp[i.first];
				if (pd[x] == 0) {
					odp[i.second] = 2;
				}
				else if ((pd[x] > 0) == (x == kr[i.second][1])) {
					odp[i.second] ^= 1;
				}
				pd[i.first] += pd[x];
				if (stp[i.first] == 1) {
					que.push(i.first);
				}
			}
		}
	}
	for (int i = 1; i <= m; ++i) {
		if (odp[i] == 0) {
			printf("R");
		}
		else if (odp[i] == 1) {
			printf("L");
		}
		else {
			printf("B");
		}
	}
	return 0;
}

Compilation message

oneway.cpp: In function 'int main()':
oneway.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:108:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
oneway.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 2 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5188 KB Output is correct
5 Correct 3 ms 5204 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5192 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 5064 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 2 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5188 KB Output is correct
5 Correct 3 ms 5204 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5192 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 5064 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 39 ms 10148 KB Output is correct
12 Correct 49 ms 11212 KB Output is correct
13 Correct 55 ms 12560 KB Output is correct
14 Correct 76 ms 14544 KB Output is correct
15 Correct 73 ms 15160 KB Output is correct
16 Correct 85 ms 16976 KB Output is correct
17 Correct 77 ms 18008 KB Output is correct
18 Correct 94 ms 17168 KB Output is correct
19 Correct 75 ms 18876 KB Output is correct
20 Correct 51 ms 11136 KB Output is correct
21 Correct 49 ms 11336 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 2 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5188 KB Output is correct
5 Correct 3 ms 5204 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5192 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 5064 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 39 ms 10148 KB Output is correct
12 Correct 49 ms 11212 KB Output is correct
13 Correct 55 ms 12560 KB Output is correct
14 Correct 76 ms 14544 KB Output is correct
15 Correct 73 ms 15160 KB Output is correct
16 Correct 85 ms 16976 KB Output is correct
17 Correct 77 ms 18008 KB Output is correct
18 Correct 94 ms 17168 KB Output is correct
19 Correct 75 ms 18876 KB Output is correct
20 Correct 51 ms 11136 KB Output is correct
21 Correct 49 ms 11336 KB Output is correct
22 Correct 100 ms 19140 KB Output is correct
23 Correct 118 ms 18068 KB Output is correct
24 Correct 115 ms 18088 KB Output is correct
25 Correct 98 ms 21412 KB Output is correct
26 Correct 104 ms 18892 KB Output is correct
27 Correct 111 ms 17968 KB Output is correct
28 Correct 36 ms 8520 KB Output is correct
29 Correct 64 ms 11980 KB Output is correct
30 Correct 63 ms 12360 KB Output is correct
31 Correct 63 ms 12280 KB Output is correct
32 Correct 92 ms 15432 KB Output is correct