oj.uz

Submission #616918

# Submission time Handle Problem Language Result Execution time Memory
616918 2022-08-01T07:41:00 Z nghiass001 One-Way Streets (CEOI17_oneway) C++17
100 / 100
 177 ms 37568 KB 
#include <bits/stdc++.h>
#define FOR(i, l, r) for(int i=(l); i<=(r); ++i)
#define REP(i, l, r) for(int i=(l); i<(r); ++i)
#define FORD(i, r, l) for(int i=(r); i>=(l); --i)
#define REPD(i, r, l)  for(int i=(r)-1; i>=(l); --i)
#define pii pair<int, int>
#define getbit(x, i) (((x) >> (i)) & 1)
using namespace std;
const int N = 1e5 + 5, M = 1e5 + 5, logN = 18, Qmax = 1e5 + 5;
int n, m, q, cnt, cnode, px[M], py[M];
int depth[N], p[N][logN], sedge[N], pre[N], parent_pair[Qmax];
int num[N], low[N], avail[N], exist[N], node[N];
vector<pii> S[N], Scc[N];
vector<int> Q, D[N], List;
char ans[M];

void Enter() {
    cin >> n >> m;
    FOR(i, 1, m) {
        int u, v;
        cin >> u >> v;
        S[u].emplace_back(v, i);
        S[v].emplace_back(u, -i);
    }
    cin >> q;
    FOR(i, 1, q) cin >> px[i] >> py[i];
}

void Tarjan(int u, int pre_edge) {
    num[u] = low[u] = ++cnt;
    Q.push_back(u);
    for(auto [v, c] : S[u]) if (-c != pre_edge) {
        if (num[v]) low[u] = min(low[u], num[v]);
        else {
            Tarjan(v, c);
            low[u] = min(low[u], low[v]);
        }
    }
    if (num[u] == low[u]) {
        ++cnode;
        int v;
        do {
            v = Q.back(); Q.pop_back();
            node[v] = cnode;
            D[cnode].push_back(v);
        } while (v != u);
    }
}

void Compress() {
    FOR(i, 1, n) if (!avail[i]) {
        Tarjan(i, 0);
    }
    FOR(i, 1, cnode) {
        exist[i] = i;
        for(int u : D[i]) for(auto [v, c] : S[u]) if (exist[node[v]] != i) {
            exist[node[v]] = i;
            Scc[i].emplace_back(node[v], c);
        }
    }
}

void DFS2(int u, int pa) {
    depth[u] = depth[pa] + 1;
    List.push_back(u);
    p[u][0] = pa;
    REP(i, 1, logN) p[u][i] = p[p[u][i - 1]][i - 1];

    for(auto [v, c] : Scc[u]) if (v != pa) {
        sedge[v] = c;
        DFS2(v, u);
    }
}

int LCA(int u, int v) {
    if (depth[u] > depth[v]) swap(u, v);
    int diff = depth[v] - depth[u];
    REPD(i, logN, 0) if (getbit(diff, i)) v = p[v][i];
    REPD(i, logN, 0) if (p[u][i] != p[v][i]) u = p[u][i], v = p[v][i];
    return (u == v ? u : p[u][0]);
}

void solve(char c1, char c2) {
    REPD(i, (int) List.size(), 0) {
        int u = List[i];
                assert(pre[u] >= 0);
        if (sedge[u] && pre[u]) {
            if (sedge[u] > 0) ans[sedge[u]] = c1;
            else ans[-sedge[u]] =  c2;
        }
        pre[p[u][0]] += pre[u];
    }
}

void Process() {
    Compress();
    FOR(i, 1, cnode) if (!depth[i]) DFS2(i, 0);

    FOR(i, 1, q) {
        int u = node[px[i]], v = node[py[i]];
        parent_pair[i] = LCA(u, v);
    }

    fill(ans + 1, ans + m + 1, 'B');
    FOR(i, 1, q) {
        int u = node[px[i]];
        ++pre[u]; --pre[parent_pair[i]];
    }
    solve('L', 'R');

    fill(pre + 1, pre + cnode + 1, 0);
    FOR(i, 1, q) {
        int u = node[py[i]];
        ++pre[u]; --pre[parent_pair[i]];
    }
    solve('R', 'L');

    cout << ans + 1;
}

int main()
{
    #define file "oneway"
    if (fopen(file".inp", "r")) {
        freopen(file".inp", "r", stdin);
        freopen(file".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    Enter();
    Process();
}

Compilation message

oneway.cpp: In function 'int main()':
oneway.cpp:125:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         freopen(file".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:126:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |         freopen(file".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7480 KB Output is correct
2 Correct 5 ms 7388 KB Output is correct
3 Correct 4 ms 7520 KB Output is correct
4 Correct 6 ms 7636 KB Output is correct
5 Correct 5 ms 7636 KB Output is correct
6 Correct 5 ms 7396 KB Output is correct
7 Correct 5 ms 7652 KB Output is correct
8 Correct 4 ms 7636 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 5 ms 7380 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7480 KB Output is correct
2 Correct 5 ms 7388 KB Output is correct
3 Correct 4 ms 7520 KB Output is correct
4 Correct 6 ms 7636 KB Output is correct
5 Correct 5 ms 7636 KB Output is correct
6 Correct 5 ms 7396 KB Output is correct
7 Correct 5 ms 7652 KB Output is correct
8 Correct 4 ms 7636 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 5 ms 7380 KB Output is correct
11 Correct 34 ms 13248 KB Output is correct
12 Correct 38 ms 14460 KB Output is correct
13 Correct 49 ms 16176 KB Output is correct
14 Correct 65 ms 20532 KB Output is correct
15 Correct 71 ms 22372 KB Output is correct
16 Correct 100 ms 30036 KB Output is correct
17 Correct 83 ms 31656 KB Output is correct
18 Correct 102 ms 30024 KB Output is correct
19 Correct 105 ms 33096 KB Output is correct
20 Correct 47 ms 14088 KB Output is correct
21 Correct 37 ms 13820 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7480 KB Output is correct
2 Correct 5 ms 7388 KB Output is correct
3 Correct 4 ms 7520 KB Output is correct
4 Correct 6 ms 7636 KB Output is correct
5 Correct 5 ms 7636 KB Output is correct
6 Correct 5 ms 7396 KB Output is correct
7 Correct 5 ms 7652 KB Output is correct
8 Correct 4 ms 7636 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 5 ms 7380 KB Output is correct
11 Correct 34 ms 13248 KB Output is correct
12 Correct 38 ms 14460 KB Output is correct
13 Correct 49 ms 16176 KB Output is correct
14 Correct 65 ms 20532 KB Output is correct
15 Correct 71 ms 22372 KB Output is correct
16 Correct 100 ms 30036 KB Output is correct
17 Correct 83 ms 31656 KB Output is correct
18 Correct 102 ms 30024 KB Output is correct
19 Correct 105 ms 33096 KB Output is correct
20 Correct 47 ms 14088 KB Output is correct
21 Correct 37 ms 13820 KB Output is correct
22 Correct 143 ms 33936 KB Output is correct
23 Correct 177 ms 32116 KB Output is correct
24 Correct 164 ms 32340 KB Output is correct
25 Correct 149 ms 37568 KB Output is correct
26 Correct 134 ms 33600 KB Output is correct
27 Correct 152 ms 32172 KB Output is correct
28 Correct 41 ms 11980 KB Output is correct
29 Correct 72 ms 16004 KB Output is correct
30 Correct 69 ms 16092 KB Output is correct
31 Correct 66 ms 16492 KB Output is correct
32 Correct 93 ms 23204 KB Output is correct