oj.uz

Submission #491129

# Submission time Handle Problem Language Result Execution time Memory
491129 2021-11-30T15:49:49 Z hollwo_pelw One-Way Streets (CEOI17_oneway) C++17
100 / 100
 75 ms 16768 KB 
/*
// is short or still long ???
hollwo_pelw's template(short)
// Note : -Dhollwo_pelw_local
*/

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;

void FAST_IO(string filein = "", string fileout = "", string fileerr = ""){
	if (fopen(filein.c_str(), "r")){
		freopen(filein.c_str(), "r", stdin);
		freopen(fileout.c_str(), "w", stdout);
#ifdef hollwo_pelw_local
		freopen(fileerr.c_str(), "w", stderr);
#endif
	}
	cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
}

void Hollwo_Pelw();

signed main(){
#ifdef hollwo_pelw_local
	FAST_IO("input.inp", "output.out", "error.err");
	auto start = chrono::steady_clock::now();
#else
	FAST_IO("hollwo_pelw.inp", "hollwo_pelw.out");
#endif
	int testcases = 1;
	// cin >> testcases;
	for (int test = 1; test <= testcases; test++){
		// cout << "Case #" << test << ": ";
		Hollwo_Pelw();
	}
#ifdef hollwo_pelw_local
	auto end = chrono::steady_clock::now();
	cout << "\nExcution time : " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif
	return 0;
}

const int N = 1e5 + 5;

struct edge_t {
	int u, v; char d = 'B';
} ed[N];

int n, m, q, tin[N], low[N], timer;
vector<pair<int, int>> adj[N];

int comp[N], compcnt;
vector<int> st;

void tarjan(int u, int p) {
	tin[u] = low[u] = ++ timer;
	st.push_back(u);

	for (auto [v, i] : adj[u]) if (i != p) {
		if (tin[v]) {
			low[u] = min(low[u], tin[v]);
		} else {
			tarjan(v, i);
			low[u] = min(low[u], low[v]);
		}
	}

	if (low[u] >= tin[u]) {
		++ compcnt;
		while (1) {
			int v = st.back();
			comp[v] = compcnt;

			st.pop_back();
			if (v == u) break ;
		}
	}
}

void __build_tree__() {
	for (int i = 1; i <= n; i++)
		adj[i].clear();

	for (int i = 1; i <= m; i++) {
		ed[i].u = comp[ed[i].u];
		ed[i].v = comp[ed[i].v];
		if (ed[i].u != ed[i].v) {
			adj[ed[i].u].emplace_back(ed[i].v, i);
			adj[ed[i].v].emplace_back(ed[i].u, i);
		}
	}

	n = compcnt;
}

int dp[N], vis[N];

void solve(int u, int p) {
	vis[u] = 1;

	for (auto [v, i] : adj[u]) if (v != p) {
		solve(v, u);

		if (dp[v] == 0)
			ed[i].d = 'B';
		else if (dp[v] < 0)
			ed[i].d = u == ed[i].u ? 'R' : 'L';
		else if (dp[v] > 0)
			ed[i].d = u == ed[i].u ? 'L' : 'R';

		dp[u] += dp[v];
	}
}

void Hollwo_Pelw() {
	cin >> n >> m;
	for (int i = 1, u, v; i <= m; i++) {
		cin >> u >> v, ed[i] = {u, v, 'B'};
		adj[u].emplace_back(v, i);
		adj[v].emplace_back(u, i);
	}

	for (int i = 1; i <= n; i++)
		if (!tin[i]) tarjan(i, 0);
	__build_tree__();

	cin >> q;
	for (int u, v; q --; )
		cin >> u >> v, dp[comp[u]] ++, dp[comp[v]] --;

	for (int i = 1; i <= n; i++)
		if (!vis[i]) solve(i, 0);

	for (int i = 1; i <= m; i++)
		cout << ed[i].d;
}

Compilation message

oneway.cpp: In function 'void FAST_IO(std::string, std::string, std::string)':
oneway.cpp:18:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |   freopen(filein.c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:19:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |   freopen(fileout.c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3788 KB Output is correct
2 Correct 2 ms 3788 KB Output is correct
3 Correct 2 ms 3916 KB Output is correct
4 Correct 2 ms 3916 KB Output is correct
5 Correct 2 ms 3916 KB Output is correct
6 Correct 2 ms 3916 KB Output is correct
7 Correct 2 ms 3916 KB Output is correct
8 Correct 2 ms 3916 KB Output is correct
9 Correct 2 ms 3856 KB Output is correct
10 Correct 2 ms 3920 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3788 KB Output is correct
2 Correct 2 ms 3788 KB Output is correct
3 Correct 2 ms 3916 KB Output is correct
4 Correct 2 ms 3916 KB Output is correct
5 Correct 2 ms 3916 KB Output is correct
6 Correct 2 ms 3916 KB Output is correct
7 Correct 2 ms 3916 KB Output is correct
8 Correct 2 ms 3916 KB Output is correct
9 Correct 2 ms 3856 KB Output is correct
10 Correct 2 ms 3920 KB Output is correct
11 Correct 31 ms 9348 KB Output is correct
12 Correct 37 ms 10204 KB Output is correct
13 Correct 46 ms 11480 KB Output is correct
14 Correct 51 ms 12424 KB Output is correct
15 Correct 50 ms 12580 KB Output is correct
16 Correct 72 ms 11844 KB Output is correct
17 Correct 55 ms 13124 KB Output is correct
18 Correct 62 ms 11708 KB Output is correct
19 Correct 49 ms 14584 KB Output is correct
20 Correct 36 ms 9928 KB Output is correct
21 Correct 35 ms 9616 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3788 KB Output is correct
2 Correct 2 ms 3788 KB Output is correct
3 Correct 2 ms 3916 KB Output is correct
4 Correct 2 ms 3916 KB Output is correct
5 Correct 2 ms 3916 KB Output is correct
6 Correct 2 ms 3916 KB Output is correct
7 Correct 2 ms 3916 KB Output is correct
8 Correct 2 ms 3916 KB Output is correct
9 Correct 2 ms 3856 KB Output is correct
10 Correct 2 ms 3920 KB Output is correct
11 Correct 31 ms 9348 KB Output is correct
12 Correct 37 ms 10204 KB Output is correct
13 Correct 46 ms 11480 KB Output is correct
14 Correct 51 ms 12424 KB Output is correct
15 Correct 50 ms 12580 KB Output is correct
16 Correct 72 ms 11844 KB Output is correct
17 Correct 55 ms 13124 KB Output is correct
18 Correct 62 ms 11708 KB Output is correct
19 Correct 49 ms 14584 KB Output is correct
20 Correct 36 ms 9928 KB Output is correct
21 Correct 35 ms 9616 KB Output is correct
22 Correct 66 ms 14020 KB Output is correct
23 Correct 73 ms 11608 KB Output is correct
24 Correct 75 ms 11800 KB Output is correct
25 Correct 69 ms 16768 KB Output is correct
26 Correct 66 ms 12940 KB Output is correct
27 Correct 68 ms 11644 KB Output is correct
28 Correct 29 ms 7108 KB Output is correct
29 Correct 51 ms 9612 KB Output is correct
30 Correct 52 ms 9764 KB Output is correct
31 Correct 56 ms 10116 KB Output is correct
32 Correct 53 ms 12248 KB Output is correct