oj.uz

Submission #427649

# Submission time Handle Problem Language Result Execution time Memory
427649 2021-06-14T18:21:19 Z JerryLiu06 One-Way Streets (CEOI17_oneway) C++17
100 / 100
 524 ms 35672 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using db = long double;
using str = string;
 
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;
 
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
 
#define mp make_pair
#define f first
#define s second

#define sz(x) (int)(x).size()
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define sor(x) sort(all(x))
#define ft front()
#define bk back()
#define pb push_back
#define pf push_front
 
#define lb lower_bound
#define ub upper_bound
 
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define R0F(i, a) ROF(i, 0, a)
#define EACH(a, x) for (auto& a : x)

const int MOD = 1e9 + 7;
const int MX = 1e5 + 10;
const ll INF = 1e18;

int N, M, P; vi adj[MX]; vpi edges;

int timer = 1; bool vis1[MX]; int in[MX], low[MX]; map<pi, bool> bridges;

int nComp = 1; int comp[MX]; vi compAdj[MX]; int val[MX], depth[MX]; bool vis2[MX];

void DFS1(int X) {
    vis1[X] = true; in[X] = low[X] = timer++;

    EACH(Y, adj[X]) {
        if (vis1[Y]) { low[X] = min(low[X], in[Y]); continue; } // Back Edge
        
        adj[Y].erase(find(all(adj[Y]), X)); DFS1(Y); low[X] = min(low[X], low[Y]);

        if (low[Y] > in[X]) bridges[{X, Y}] = bridges[{Y, X}] = true;
    }
}
void genComp(int X, int label) {
    comp[X] = label; EACH(Y, adj[X]) if (!comp[Y] && !bridges[{X, Y}]) genComp(Y, label);
}

void DFS2(int X, int P) {
    vis2[X] = true; EACH(Y, compAdj[X]) if (Y != P) { depth[Y] = depth[X] + 1; DFS2(Y, X); val[X] += val[Y]; }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> N >> M; F0R(i, M) { int A, B; cin >> A >> B; adj[A].pb(B), adj[B].pb(A); edges.pb({A, B}); }

    FOR(i, 1, N + 1) if (!vis1[i]) DFS1(i); FOR(i, 1, N + 1) if (!comp[i]) genComp(i, nComp++);

    EACH(P, edges) if (bridges[{P.f, P.s}]) {
        int A = comp[P.f], B = comp[P.s]; compAdj[A].pb(B), compAdj[B].pb(A);
    }
    cin >> P; F0R(i, P) {
        int A, B; cin >> A >> B; val[comp[A]]++, val[comp[B]]--;
    }
    FOR(i, 1, nComp) if (!vis2[i]) DFS2(i, 0);

    F0R(i, M) { pi E = edges[i];
        if (!bridges[{E.f, E.s}]) { cout << "B"; continue; }

        int A = comp[E.f], B = comp[E.s]; int LOW = depth[A] > depth[B] ? A : B;

        if (val[LOW] == 0) { cout << "B"; continue; }

        int cnt = 0; if (depth[A] > depth[B]) cnt++; if (val[LOW] > 0) cnt++;

        if (cnt % 2) cout << "L"; else cout << "R";
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5032 KB Output is correct
3 Correct 4 ms 5196 KB Output is correct
4 Correct 5 ms 5196 KB Output is correct
5 Correct 5 ms 5196 KB Output is correct
6 Correct 5 ms 5088 KB Output is correct
7 Correct 6 ms 5316 KB Output is correct
8 Correct 6 ms 5196 KB Output is correct
9 Correct 6 ms 5068 KB Output is correct
10 Correct 4 ms 5068 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5032 KB Output is correct
3 Correct 4 ms 5196 KB Output is correct
4 Correct 5 ms 5196 KB Output is correct
5 Correct 5 ms 5196 KB Output is correct
6 Correct 5 ms 5088 KB Output is correct
7 Correct 6 ms 5316 KB Output is correct
8 Correct 6 ms 5196 KB Output is correct
9 Correct 6 ms 5068 KB Output is correct
10 Correct 4 ms 5068 KB Output is correct
11 Correct 140 ms 17176 KB Output is correct
12 Correct 164 ms 18808 KB Output is correct
13 Correct 180 ms 20912 KB Output is correct
14 Correct 252 ms 23968 KB Output is correct
15 Correct 285 ms 24888 KB Output is correct
16 Correct 408 ms 28108 KB Output is correct
17 Correct 347 ms 30428 KB Output is correct
18 Correct 524 ms 28196 KB Output is correct
19 Correct 314 ms 31992 KB Output is correct
20 Correct 150 ms 19180 KB Output is correct
21 Correct 136 ms 18680 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5032 KB Output is correct
3 Correct 4 ms 5196 KB Output is correct
4 Correct 5 ms 5196 KB Output is correct
5 Correct 5 ms 5196 KB Output is correct
6 Correct 5 ms 5088 KB Output is correct
7 Correct 6 ms 5316 KB Output is correct
8 Correct 6 ms 5196 KB Output is correct
9 Correct 6 ms 5068 KB Output is correct
10 Correct 4 ms 5068 KB Output is correct
11 Correct 140 ms 17176 KB Output is correct
12 Correct 164 ms 18808 KB Output is correct
13 Correct 180 ms 20912 KB Output is correct
14 Correct 252 ms 23968 KB Output is correct
15 Correct 285 ms 24888 KB Output is correct
16 Correct 408 ms 28108 KB Output is correct
17 Correct 347 ms 30428 KB Output is correct
18 Correct 524 ms 28196 KB Output is correct
19 Correct 314 ms 31992 KB Output is correct
20 Correct 150 ms 19180 KB Output is correct
21 Correct 136 ms 18680 KB Output is correct
22 Correct 339 ms 31648 KB Output is correct
23 Correct 362 ms 29220 KB Output is correct
24 Correct 461 ms 29296 KB Output is correct
25 Correct 346 ms 35672 KB Output is correct
26 Correct 345 ms 30968 KB Output is correct
27 Correct 431 ms 29368 KB Output is correct
28 Correct 78 ms 8500 KB Output is correct
29 Correct 190 ms 19776 KB Output is correct
30 Correct 165 ms 19956 KB Output is correct
31 Correct 180 ms 20404 KB Output is correct
32 Correct 216 ms 24480 KB Output is correct