oj.uz

답안 #319881

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
319881 2020-11-06T16:12:37 Z parsabahrami One-Way Streets (CEOI17_oneway) C++17
0 / 100
 5 ms 3820 KB 
//! The Leader Of Retards Bemola
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
 
using namespace std;
 
typedef int ll;
typedef pair<ll, ll> pll;
 
#define sz(x)                       (ll) x.size()
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
 
ll Pow(ll a, ll b, ll md, ll ans = 1) {
    for (; b; b >>= 1, a = a * a % md)
        if (b & 1)
            ans = ans * a % md;
    return ans % md;
}
const ll MAXN = 1e5 + 2;
const ll LOG  = 19;
const ll MOD  = 1e9 + 7;
ll par[LOG][MAXN], B[MAXN], P[MAXN], M[MAXN], H[MAXN], ps[2][MAXN], n, m, k;
vector<pll> adj[MAXN]; pll E[MAXN];
 
void preDFS(ll v, ll p = 0) {
    M[v] = MOD;
    H[v] = H[p] + 1;
    for (pll u : adj[v]) {
        if (H[u.F] == 0) {
            preDFS(u.F, v);
            M[v] = min(M[v], M[u.F]);
            if (M[u.F] > H[v]) B[u.S] = 1;
        } else if (u.F != p) {
            M[v] = min(M[v], H[u.F]);
        }
    }
}
 
void DFS(ll v, ll p = 0) {
	H[v] = H[p] + 1;
	if (p == -1) par[0][v] = v;
	for (ll i = 1; i < LOG; i++) {
		par[i][v] = par[i - 1][par[i - 1][v]];
	}
	for (auto[u, tmp] : adj[v]) {
		if (H[u] == 0) {
			par[0][u] = v;
			DFS(u, v);
		}
	}
}
 
ll getpar(ll v, ll h) {
	for (ll i = LOG - 1; i--;) {
		if (h & (1 << i)) v = par[i][v];
	}
	return v;
}
 
ll LCA(ll u, ll v) {
	if (H[u] < H[v]) swap(u, v);
	u = getpar(u, H[u] - H[v]);
	if (u == v) return v;
	for (ll i = LOG - 1; i--;) {
		if (par[i][v] != par[i][u]) {
			v = par[i][v], u = par[i][u];
		}
	}
	return par[0][v];
}
 
void calcDFS(ll v, ll p = 0) {
    H[v] = H[p] + 1;
	for (auto[u, tmp] : adj[v]) {
		if (H[u] == 0) {
			calcDFS(u, v);
			ps[0][v] += ps[0][u];
			ps[1][v] += ps[1][u];
		}
	}
}
 
ll Find(ll v) {
	return P[v] == -1 ? v : P[v] = Find(P[v]);
}
 
ll Union(ll u, ll v) {
	v = Find(v), u = Find(u);
	if (u == v) return 0;
	P[u] = v;
	return 1;
}
 
int main() {
	fill(P, P + MAXN, -1);
	scanf("%d%d", &n, &m);
	for (ll i = 1; i <= m; i++) {
		ll u, v; scanf("%d%d", &u, &v);
		adj[v].push_back({u, i});
		adj[u].push_back({v, i}); E[i] = {u, v};
	}
	for (ll i = 1; i <= n; i++) if (H[i] == 0) preDFS(i);
	fill(H, H + MAXN, 0);
	for (ll i = 1; i <= m; i++) {
		if (B[i] == 0) Union(E[i].F, E[i].S);
	}
	for (ll i = 1; i <= n; i++) adj[i].clear(), adj[i].shrink_to_fit();
	for (ll i = 1; i <= m; i++) {
		if (B[i]) {
			ll u = Find(E[i].F), v = Find(E[i].S);
			adj[u].push_back({v, 0});
			adj[v].push_back({u, 0});
		}
	}
	for (ll i = 1; i <= n; i++) {
		if (H[Find(i)]) continue;
		DFS(Find(i));
	}
	scanf("%d", &k);
	for (ll i = 1; i <= k; i++) {
		ll x, y, l; scanf("%d%d", &x, &y); x = Find(x), y = Find(y);
		l = LCA(x, y);
		ps[0][x]++, ps[0][l]--;
		ps[1][y]++, ps[1][l]--;
	}
	fill(H, H + MAXN, 0);
	for (ll i = 1; i <= n; i++) {
		if (H[Find(i)]) continue;
		calcDFS(Find(i));
	}
	for (ll i = 1; i <= m; i++) {
		ll u = E[i].F, v = E[i].S, f = 0; u = Find(u), v = Find(v);
		if (H[u] < H[v]) swap(u, v), f = 1;
		if (ps[0][u] && ps[1][u]) printf("B");
		else if (B[i] == 0) printf("B");
		else if (ps[0][u] == 0 && ps[1][u] == 0) printf("B");
		else if (ps[0][u]) {
			if (f)  printf("L");
			else printf("R");
		} else {
			if (f)  printf("R");
			else printf("L");
		}
	}
	printf("\n");
    return 0;
}

Compilation message

oneway.cpp: In function 'int main()':
oneway.cpp:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   98 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:100:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  100 |   ll u, v; scanf("%d%d", &u, &v);
      |            ~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:121:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  121 |  scanf("%d", &k);
      |  ~~~~~^~~~~~~~~~
oneway.cpp:123:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  123 |   ll x, y, l; scanf("%d%d", &x, &y); x = Find(x), y = Find(y);
      |               ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3564 KB Output is correct
2 Correct 3 ms 3564 KB Output is correct
3 Correct 3 ms 3692 KB Output is correct
4 Correct 4 ms 3820 KB Output is correct
5 Correct 4 ms 3712 KB Output is correct
6 Correct 3 ms 3692 KB Output is correct
7 Correct 4 ms 3692 KB Output is correct
8 Correct 5 ms 3692 KB Output is correct
9 Incorrect 4 ms 3692 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3564 KB Output is correct
2 Correct 3 ms 3564 KB Output is correct
3 Correct 3 ms 3692 KB Output is correct
4 Correct 4 ms 3820 KB Output is correct
5 Correct 4 ms 3712 KB Output is correct
6 Correct 3 ms 3692 KB Output is correct
7 Correct 4 ms 3692 KB Output is correct
8 Correct 5 ms 3692 KB Output is correct
9 Incorrect 4 ms 3692 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3564 KB Output is correct
2 Correct 3 ms 3564 KB Output is correct
3 Correct 3 ms 3692 KB Output is correct
4 Correct 4 ms 3820 KB Output is correct
5 Correct 4 ms 3712 KB Output is correct
6 Correct 3 ms 3692 KB Output is correct
7 Correct 4 ms 3692 KB Output is correct
8 Correct 5 ms 3692 KB Output is correct
9 Incorrect 4 ms 3692 KB Output isn't correct
10 Halted 0 ms 0 KB -