oj.uz

Submission #559840

# Submission time Handle Problem Language Result Execution time Memory
559840 2022-05-10T17:45:11 Z GioChkhaidze One-Way Streets (CEOI17_oneway) C++14
100 / 100
 178 ms 33664 KB 
#include <bits/stdc++.h>

#define pb push_back
#define f first
#define s second

using namespace std;

const int N = 1e5 + 5;

char ans[N];
bool f[N], brd[N];
int n, m, q, timer, depth, ts;
int a[N], b[N], disc[N], low[N], p[N], sz[N], dep[N], in[N], out[N], W[N][4], Pr[N][20];
vector < int > bridges;
vector < pair < int , int > > v[N], g[N];

void dfs(int x, int edg) {
	f[x] = true;
	disc[x] = low[x] = ++timer;
	for (int i = 0; i < v[x].size(); ++i) {
		int to = v[x][i].f, ed = v[x][i].s;
		if (ed == edg) continue;
		if (!f[to]) {
			dfs(to, ed);
			low[x] = min(low[x], low[to]);
			if (low[to] > disc[x]) {
				brd[ed] = true;
				bridges.pb(ed);
			}
		}
			else {
			low[x] = min(low[x], disc[to]);		
		}
	}
}

int P(int x) {
	if (p[x] == x) return x;
	return p[x] = P(p[x]);
}

bool is_anc(int a, int b) {
	return in[a] <= in[b] && out[b] <= out[a];
}

int lca(int a, int b) {
	if (is_anc(a, b)) return a;
	for (int i = 17; i >= 0; --i) 
		if (!is_anc(Pr[a][i], b)) a = Pr[a][i];
	return Pr[a][0];
}

void wfs(int x, int p) {
	f[x] = true;
	in[x] = ++ts;
	Pr[x][0] = p;
	for (int j = 1; j < 18; ++j) {
		Pr[x][j] = Pr[Pr[x][j - 1]][j - 1];
	}
	for (int i = 0; i < g[x].size(); ++i) {
		int to = g[x][i].f;
		if (to != p) wfs(to, x);
	}
	out[x] = ts;
}

void ufs(int x, int edg) {
	f[x] = true;
	for (int i = 0; i < g[x].size(); ++i) {
		int to = g[x][i].f, ed = g[x][i].s;
		if (ed == edg) continue;
		ufs(to, ed);
		W[x][0] += W[to][0];
		W[x][1] += W[to][1];
	}
	if (edg != -1){
		int A = P(a[edg]), B = P(b[edg]);
		if (W[x][0] > 0) {
			if (B == x) ans[edg] = 'L';
				else 
			if (A == x) ans[edg] = 'R';	
		}
			else
		if (W[x][1] > 0) {
			if (B == x) ans[edg] = 'R';
				else 
			if (A == x) ans[edg] = 'L';
		}
	}
}

main () {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		ans[i] = 'B';
		cin >> a[i] >> b[i];
		v[a[i]].pb({b[i], i});
		v[b[i]].pb({a[i], i});
	}
	
	for (int i = 1; i <= n; ++i) 
		if (!f[i]) dfs(i, -1);
	
	for (int i = 1; i <= n; ++i) 
		p[i] = i, sz[i] = 1, f[i] = 0;
	
	for (int i = 1; i <= m; ++i) {
		if (brd[i]) continue;
		int A = P(a[i]), B = P(b[i]);
		if (A == B) continue;
		if (sz[A] < sz[B]) swap(A, B);
		sz[A] += sz[B];
		p[B] = A;
	}
	
	vector < int > nd;
	for (int i = 0; i < bridges.size(); ++i) {
		int id = bridges[i];
		int A = P(a[id]);
		int B = P(b[id]);
		g[A].pb({B, id});
		g[B].pb({A, id});
		if (!f[A]) nd.pb(A), f[A] = true;
		if (!f[B]) nd.pb(B), f[B] = true;
	}
	
	for (int i = 0; i < nd.size(); ++i) 
		f[nd[i]] = false;
	
	for (int i = 0; i < nd.size(); ++i) 
		if (!f[nd[i]]) wfs(nd[i], nd[i]);	
	
	cin >> q;
	for (int i = 1; i <= q; ++i) {
		int x, y, z;
		cin >> x >> y;
		x = P(x), y = P(y);
		if (x == y) continue;
		z = lca(x, y);
		--W[z][0], ++W[x][0];
		--W[z][1], ++W[y][1];
	}
	
	for (int i = 0; i < nd.size(); ++i) 
		f[nd[i]] = false;
	
	for (int i = 0; i < nd.size(); ++i) 
		if (!f[nd[i]]) ufs(nd[i], -1);	
	
	for (int i = 1; i <= m; ++i) 
		cout << ans[i];
}

Compilation message

oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:21: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]
   21 |  for (int i = 0; i < v[x].size(); ++i) {
      |                  ~~^~~~~~~~~~~~~
oneway.cpp: In function 'void wfs(int, int)':
oneway.cpp:61: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]
   61 |  for (int i = 0; i < g[x].size(); ++i) {
      |                  ~~^~~~~~~~~~~~~
oneway.cpp: In function 'void ufs(int, int)':
oneway.cpp:70: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]
   70 |  for (int i = 0; i < g[x].size(); ++i) {
      |                  ~~^~~~~~~~~~~~~
oneway.cpp: At global scope:
oneway.cpp:93:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   93 | main () {
      | ^~~~
oneway.cpp: In function 'int main()':
oneway.cpp:120:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |  for (int i = 0; i < bridges.size(); ++i) {
      |                  ~~^~~~~~~~~~~~~~~~
oneway.cpp:130:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |  for (int i = 0; i < nd.size(); ++i)
      |                  ~~^~~~~~~~~~~
oneway.cpp:133:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |  for (int i = 0; i < nd.size(); ++i)
      |                  ~~^~~~~~~~~~~
oneway.cpp:147:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |  for (int i = 0; i < nd.size(); ++i)
      |                  ~~^~~~~~~~~~~
oneway.cpp:150:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |  for (int i = 0; i < nd.size(); ++i)
      |                  ~~^~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 4 ms 5076 KB Output is correct
3 Correct 4 ms 5204 KB Output is correct
4 Correct 4 ms 5284 KB Output is correct
5 Correct 3 ms 5332 KB Output is correct
6 Correct 3 ms 5036 KB Output is correct
7 Correct 4 ms 5288 KB Output is correct
8 Correct 5 ms 5292 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 4 ms 5156 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 4 ms 5076 KB Output is correct
3 Correct 4 ms 5204 KB Output is correct
4 Correct 4 ms 5284 KB Output is correct
5 Correct 3 ms 5332 KB Output is correct
6 Correct 3 ms 5036 KB Output is correct
7 Correct 4 ms 5288 KB Output is correct
8 Correct 5 ms 5292 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 4 ms 5156 KB Output is correct
11 Correct 40 ms 11596 KB Output is correct
12 Correct 46 ms 13944 KB Output is correct
13 Correct 57 ms 19148 KB Output is correct
14 Correct 76 ms 23628 KB Output is correct
15 Correct 140 ms 25208 KB Output is correct
16 Correct 130 ms 27328 KB Output is correct
17 Correct 115 ms 28924 KB Output is correct
18 Correct 94 ms 27228 KB Output is correct
19 Correct 107 ms 30360 KB Output is correct
20 Correct 44 ms 12288 KB Output is correct
21 Correct 44 ms 15756 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 4 ms 5076 KB Output is correct
3 Correct 4 ms 5204 KB Output is correct
4 Correct 4 ms 5284 KB Output is correct
5 Correct 3 ms 5332 KB Output is correct
6 Correct 3 ms 5036 KB Output is correct
7 Correct 4 ms 5288 KB Output is correct
8 Correct 5 ms 5292 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 4 ms 5156 KB Output is correct
11 Correct 40 ms 11596 KB Output is correct
12 Correct 46 ms 13944 KB Output is correct
13 Correct 57 ms 19148 KB Output is correct
14 Correct 76 ms 23628 KB Output is correct
15 Correct 140 ms 25208 KB Output is correct
16 Correct 130 ms 27328 KB Output is correct
17 Correct 115 ms 28924 KB Output is correct
18 Correct 94 ms 27228 KB Output is correct
19 Correct 107 ms 30360 KB Output is correct
20 Correct 44 ms 12288 KB Output is correct
21 Correct 44 ms 15756 KB Output is correct
22 Correct 166 ms 30064 KB Output is correct
23 Correct 172 ms 28288 KB Output is correct
24 Correct 159 ms 28504 KB Output is correct
25 Correct 136 ms 33664 KB Output is correct
26 Correct 178 ms 29732 KB Output is correct
27 Correct 170 ms 28376 KB Output is correct
28 Correct 36 ms 9176 KB Output is correct
29 Correct 69 ms 13036 KB Output is correct
30 Correct 72 ms 14124 KB Output is correct
31 Correct 66 ms 13516 KB Output is correct
32 Correct 82 ms 23520 KB Output is correct