oj.uz

Submission #644430

# Submission time Handle Problem Language Result Execution time Memory
644430 2022-09-24T16:55:31 Z ghostwriter One-Way Streets (CEOI17_oneway) C++14
100 / 100
 146 ms 30620 KB 
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.h>
#endif
#define ft front
#define bk back
#define st first
#define nd second
#define ins insert
#define ers erase
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define bg begin
#define ed end
#define all(x) (x).bg(), (x).ed()
#define sz(x) (int)(x).size()
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
template<typename T> T gcd(T a, T b) { return (b == 0? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
#define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
#define EACH(i, x) for (auto &(i) : (x))
#define WHILE while
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
    Tran The Bao
    VOI23 gold medal
*/
const int N = 1e5 + 5;
int n, m, p, h[N], P[N][17], pos[N], s[N], c[N], tin[N], low[N], bridge[N], scc[N], cnt = 0, cnt1 = 0;
pi f[N];
pi e[N];
vi adj[N], adj1[N];
void upd(int ps, pi v) { for (int i = ps; i <= cnt; i += (i & -i)) { f[i].st += v.st; f[i].nd += v.nd; } }
pi get(int ps) { pi rs = {0, 0}; for (int i = ps; i >= 1; i -= (i & -i)) { rs.st += f[i].st; rs.nd += f[i].nd; } return rs; }
void dfs(int u, int p) {
	tin[u] = low[u] = ++cnt;
	EACH(j, adj[u]) {
		if (j == p) continue;
		int v = (e[j].st == u? e[j].nd : e[j].st);
		if (tin[v]) low[u] = min(low[u], tin[v]);
		else {
			dfs(v, j);
			low[u] = min(low[u], low[v]);
			if (low[v] > tin[u]) bridge[j] = 1;
		}
	}
}
void dfs1(int u) {
	EACH(j, adj[u]) {
		int v = (e[j].st == u? e[j].nd : e[j].st);
		if (scc[v]) continue;
		if (bridge[j]) {
			scc[v] = ++cnt;
			adj1[scc[u]].pb(scc[v]);
			adj1[scc[v]].pb(scc[u]);
			dfs1(v);
		}
		else {
			scc[v] = scc[u];
			dfs1(v);
		}
	}
}
void dfs2(int u, int p) {
	c[u] = 1;
	h[u] = h[p] + 1;
	P[u][0] = p;
	pos[u] = ++cnt1;
	s[u] = 1;
	EACH(v, adj1[u]) {
		if (v == p) continue;
		dfs2(v, u);
		s[u] += s[v];
	}
}
void build() {
	FOR(j, 1, 16)
	FOR(i, 1, cnt)
		P[i][j] = P[P[i][j - 1]][j - 1];
}
int lca(int a, int b) {
	if (h[a] > h[b]) swap(a, b);
	int diff = h[b] - h[a];
	FOR(i, 0, 16)
		if (diff & (1 << i))
			b = P[b][i];
	if (a == b) return a;
	FOS(i, 16, 0)
		if (P[a][i] != P[b][i]) {
			a = P[a][i];
			b = P[b][i];
		}
	return P[a][0];
}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);
    cin >> n >> m;
    FOR(i, 1, m) {
    	int u, v;
    	cin >> u >> v;
    	e[i] = {u, v};
    	adj[u].pb(i);
    	adj[v].pb(i);
    }
    FOR(i, 1, n) {
    	if (tin[i]) continue;
    	dfs(i, 0);
    }
    cnt = 0;
    FOR(i, 1, n) {
    	if (scc[i]) continue;
    	scc[i] = ++cnt;
    	dfs1(i);
    }
    FOR(i, 1, cnt) {
    	if (c[i]) continue;
    	dfs2(i, 0);
    }
    build();
    cin >> p;
    FOR(i, 1, p) {
    	int x, y;
    	cin >> x >> y;
    	x = scc[x];
    	y = scc[y];
    	if (x == y) continue;
    	int LCA = lca(x, y);
    	upd(pos[x], {1, 0});
    	upd(pos[y], {0, 1});
    	upd(pos[LCA], {-1, -1});
    }
    FOR(i, 1, m)
    	if (!bridge[i]) cout << 'B';
    	else {
    		int u = e[i].st, v = e[i].nd;
    		u = scc[u];
    		v = scc[v];
    		if (P[u][0] == v) swap(u, v);
    		pi f = get(pos[v] + s[v] - 1), s = get(pos[v] - 1);
    		f.st -= s.st;
    		f.nd -= s.nd;
    		if (!f.st && !f.nd) cout << 'B';
    		else if (f.st) {
    			if (scc[e[i].st] == u) cout << 'L';
    			else cout << 'R';
    		}
    		else {
    			if (scc[e[i].st] == u) cout << 'R';
    			else cout << 'L';
    		}
    	}
    return 0;
}
/*
5 6
1 2
1 2
4 3
2 3
1 3
5 1
2
4 5
1 3
*/
/*
From Benq:
    stuff you should look for
        * int overflow, array bounds
        * special cases (n=1?)
        * do smth instead of nothing and stay organized
        * WRITE STUFF DOWN
        * DON'T GET STUCK ON ONE APPROACH
*/

Compilation message

oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:32:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   32 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
oneway.cpp:50:2: note: in expansion of macro 'EACH'
   50 |  EACH(j, adj[u]) {
      |  ^~~~
oneway.cpp: In function 'void dfs1(int)':
oneway.cpp:32:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   32 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
oneway.cpp:62:2: note: in expansion of macro 'EACH'
   62 |  EACH(j, adj[u]) {
      |  ^~~~
oneway.cpp: In function 'void dfs2(int, int)':
oneway.cpp:32:31: warning: unnecessary parentheses in declaration of 'v' [-Wparentheses]
   32 | #define EACH(i, x) for (auto &(i) : (x))
      |                               ^
oneway.cpp:83:2: note: in expansion of macro 'EACH'
   83 |  EACH(v, adj1[u]) {
      |  ^~~~
oneway.cpp: In function 'void build()':
oneway.cpp:30:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   30 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
oneway.cpp:90:2: note: in expansion of macro 'FOR'
   90 |  FOR(j, 1, 16)
      |  ^~~
oneway.cpp:30:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   30 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
oneway.cpp:91:2: note: in expansion of macro 'FOR'
   91 |  FOR(i, 1, cnt)
      |  ^~~
oneway.cpp: In function 'int lca(int, int)':
oneway.cpp:30:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   30 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
oneway.cpp:97:2: note: in expansion of macro 'FOR'
   97 |  FOR(i, 0, 16)
      |  ^~~
oneway.cpp:31:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   31 | #define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
      |                               ^
oneway.cpp:101:2: note: in expansion of macro 'FOS'
  101 |  FOS(i, 16, 0)
      |  ^~~
oneway.cpp: In function 'int main()':
oneway.cpp:30:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   30 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
oneway.cpp:113:5: note: in expansion of macro 'FOR'
  113 |     FOR(i, 1, m) {
      |     ^~~
oneway.cpp:30:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   30 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
oneway.cpp:120:5: note: in expansion of macro 'FOR'
  120 |     FOR(i, 1, n) {
      |     ^~~
oneway.cpp:30:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   30 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
oneway.cpp:125:5: note: in expansion of macro 'FOR'
  125 |     FOR(i, 1, n) {
      |     ^~~
oneway.cpp:30:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   30 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
oneway.cpp:130:5: note: in expansion of macro 'FOR'
  130 |     FOR(i, 1, cnt) {
      |     ^~~
oneway.cpp:30:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   30 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
oneway.cpp:136:5: note: in expansion of macro 'FOR'
  136 |     FOR(i, 1, p) {
      |     ^~~
oneway.cpp:30:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   30 | #define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
      |                               ^
oneway.cpp:147:5: note: in expansion of macro 'FOR'
  147 |     FOR(i, 1, m)
      |     ^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 5204 KB Output is correct
5 Correct 3 ms 5276 KB Output is correct
6 Correct 3 ms 5040 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 3 ms 5172 KB Output is correct
9 Correct 3 ms 5116 KB Output is correct
10 Correct 3 ms 5040 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 2 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5204 KB Output is correct
5 Correct 3 ms 5276 KB Output is correct
6 Correct 3 ms 5040 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 3 ms 5172 KB Output is correct
9 Correct 3 ms 5116 KB Output is correct
10 Correct 3 ms 5040 KB Output is correct
11 Correct 36 ms 10160 KB Output is correct
12 Correct 40 ms 11628 KB Output is correct
13 Correct 51 ms 13492 KB Output is correct
14 Correct 64 ms 16956 KB Output is correct
15 Correct 70 ms 18236 KB Output is correct
16 Correct 88 ms 23416 KB Output is correct
17 Correct 73 ms 25820 KB Output is correct
18 Correct 85 ms 23884 KB Output is correct
19 Correct 80 ms 27144 KB Output is correct
20 Correct 44 ms 11032 KB Output is correct
21 Correct 38 ms 11212 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 2 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5204 KB Output is correct
5 Correct 3 ms 5276 KB Output is correct
6 Correct 3 ms 5040 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 3 ms 5172 KB Output is correct
9 Correct 3 ms 5116 KB Output is correct
10 Correct 3 ms 5040 KB Output is correct
11 Correct 36 ms 10160 KB Output is correct
12 Correct 40 ms 11628 KB Output is correct
13 Correct 51 ms 13492 KB Output is correct
14 Correct 64 ms 16956 KB Output is correct
15 Correct 70 ms 18236 KB Output is correct
16 Correct 88 ms 23416 KB Output is correct
17 Correct 73 ms 25820 KB Output is correct
18 Correct 85 ms 23884 KB Output is correct
19 Correct 80 ms 27144 KB Output is correct
20 Correct 44 ms 11032 KB Output is correct
21 Correct 38 ms 11212 KB Output is correct
22 Correct 146 ms 26968 KB Output is correct
23 Correct 143 ms 25192 KB Output is correct
24 Correct 140 ms 25236 KB Output is correct
25 Correct 130 ms 30620 KB Output is correct
26 Correct 124 ms 26492 KB Output is correct
27 Correct 125 ms 25160 KB Output is correct
28 Correct 28 ms 8148 KB Output is correct
29 Correct 59 ms 11692 KB Output is correct
30 Correct 63 ms 12116 KB Output is correct
31 Correct 58 ms 12268 KB Output is correct
32 Correct 84 ms 18608 KB Output is correct