Submission #320586

#	Time	Username	Problem	Language	Result	Execution time	Memory
320586		parsabahrami	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	140 ms	17932 KiB

oneway

//! The Leader Of Retards Bemola
#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
#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 + 10;
const ll LOG  = 18;
const ll MOD  = 1e9 + 7;
ll A[MAXN], B[MAXN], P[MAXN], M[MAXN], L[MAXN], ps[MAXN], mark[MAXN], n, m, k, timer;
vector<pll> adj[MAXN]; pll E[MAXN];

void preDFS(ll v, ll p = -1) {
    mark[v] = 1;
    M[v] = L[v] = ++timer;
    for (pll u : adj[v]) {
        if (u.S == p) continue;
        if (L[u.F] != 0) {
        	M[v] = min(M[v], L[u.F]);
        } else {
        	preDFS(u.F, u.S);
        	if (M[u.F] > L[v]) B[u.S] = 1;
    		M[v] = min(M[v], M[u.F]);
        }
    }
}

ll Find(ll v) { return P[v] == -1 ? v : P[v] = Find(P[v]); }
 
void Union(ll u, ll v) { 
	u = Find(u), v = Find(v);
	return (u == v ? void() : void(P[u] = v));
}

void DFS(ll v, ll p = -1) {
	mark[v] = 1;
	for (pll u : adj[v]) {
		if (u.F == p) continue;
		DFS(u.F, v);
		if (ps[u.F] < 0) {
			if (Find(E[u.S].F) == v) A[u.S] = 1;
			else A[u.S] = -1;
		} else if (ps[u.F] > 0) {
			if (Find(E[u.S].F) == v) A[u.S] = -1;
			else A[u.S] = 1;
		}
		ps[v] += ps[u.F];
	}
}

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 (mark[i] == 0) preDFS(i);
	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, i});
			adj[v].push_back({u, i});
		}
	}
	scanf("%d", &k);
	for (ll i = 1; i <= k; i++) {
		ll u, v; scanf("%d%d", &u, &v);
		u = Find(u), v = Find(v);
		ps[u]++, ps[v]--;
	}
	fill(mark, mark + MAXN, 0);
	for (ll i = 1; i <= n; i++) {
		if (mark[Find(i)] == 0) DFS(Find(i));
	}
	for (ll i = 1; i <= m; i++) {
		if (A[i] == 1) printf("R");
		else if (A[i] == -1) printf("L");
		else printf("B");
	}
	printf("\n");
    return 0;
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:70:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   70 |   ll u, v; scanf("%d%d", &u, &v);
      |            ~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   86 |  scanf("%d", &k);
      |  ~~~~~^~~~~~~~~~
oneway.cpp:88:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   88 |   ll u, v; scanf("%d%d", &u, &v);
      |            ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40