oj.uz

Submission #259204

# Submission time Handle Problem Language Result Execution time Memory
259204 2020-08-07T11:31:16 Z dolphingarlic One-Way Streets (CEOI17_oneway) C++14
0 / 100
 5 ms 5248 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

vector<pair<int, int>> graph[100001], compressed[100001];
pair<int, int> edges[100001];
bool visited[100001], bidir[100001], to_right[100001];
int tin[100001], tout[100001], low[100001], timer;
int cmp[100001], bit[100001];

int find(int A) {
    while (cmp[A] != A) cmp[A] = cmp[cmp[A]], A = cmp[A];
    return A;
}
void onion(int A, int B) {
    cmp[find(A)] = find(B);
}

void bridge_dfs(int node, int parent = 0) {
    visited[node] = true;
    tin[node] = low[node] = ++timer;
    for (pair<int, int> i : graph[node]) if (i.first != parent) {
        if (visited[i.first]) low[node] = min(low[node], tin[i.first]);
        else {
            bridge_dfs(i.first, node);
            low[node] = min(low[node], low[i.first]);
            if (low[i.first] > tin[node]) bidir[i.second] = true;
            else onion(node, i.first);
        }
    }
}

void lca_dfs(int node, int parent = 0) {
    visited[node] = true;
    tin[node] = ++timer;
    for (pair<int, int> i : compressed[node]) if (i.first != parent) {
        lca_dfs(i.first, node);
    }
    tout[node] = timer;
}

void update(int pos, int val) {
    for (; pos <= timer; pos += (pos & (-pos))) bit[pos] += val;
}
int query(int a, int b) {
    int ans = 0;
    for (; b; b -= (b & (-b))) ans += bit[b];
    for (a--; a; a -= (a & -a)) ans -= bit[a];
    return ans;
}

void dir_dfs(int node, int parent = 0) {
    visited[node] = true;
    for (pair<int, int> i : compressed[node]) if (i.first != parent) {
        int weight = query(tin[i.first], tout[i.first]);
        if (!weight) bidir[abs(i.second)] = false;
        else if (weight < 0) to_right[abs(i.second)] = i.second > 0;
        else to_right[abs(i.second)] = i.second < 0;
        dir_dfs(i.first, node);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    iota(cmp + 1, cmp + n + 1, 1);
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back({v, i});
        graph[v].push_back({u, i});
        edges[i] = {u, v};
    }
    timer = 0;
    for (int i = 1; i <= n; i++) if (!visited[i]) bridge_dfs(i);
    for (int i = 1; i <= m; i++) if (bidir[i]) {
        compressed[find(edges[i].first)].push_back({find(edges[i].second), i});
        compressed[find(edges[i].second)].push_back({find(edges[i].first), -i});
    }
    timer = 0;
    memset(visited, 0, sizeof visited);
    for (int i = 1; i <= n; i++) if (!visited[find(i)]) lca_dfs(find(i));

    int p;
    cin >> p;
    while (p--) {
        int a, b;
        cin >> a >> b;
        update(tin[find(a)], 1);
        update(tin[find(b)], -1);
    }

    memset(visited, 0, sizeof visited);
    for (int i = 1; i <= n; i++) if (!visited[find(i)]) dir_dfs(find(i));
    for (int i = 1; i <= m; i++) {
        cout << (bidir[i] ? (to_right[i] ? 'R' : 'L') : 'B');
    }
    return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5120 KB Output is correct
2 Correct 4 ms 5120 KB Output is correct
3 Correct 4 ms 5248 KB Output is correct
4 Correct 4 ms 5248 KB Output is correct
5 Correct 4 ms 5248 KB Output is correct
6 Correct 4 ms 5248 KB Output is correct
7 Correct 4 ms 5248 KB Output is correct
8 Correct 5 ms 5248 KB Output is correct
9 Incorrect 4 ms 5248 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5120 KB Output is correct
2 Correct 4 ms 5120 KB Output is correct
3 Correct 4 ms 5248 KB Output is correct
4 Correct 4 ms 5248 KB Output is correct
5 Correct 4 ms 5248 KB Output is correct
6 Correct 4 ms 5248 KB Output is correct
7 Correct 4 ms 5248 KB Output is correct
8 Correct 5 ms 5248 KB Output is correct
9 Incorrect 4 ms 5248 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5120 KB Output is correct
2 Correct 4 ms 5120 KB Output is correct
3 Correct 4 ms 5248 KB Output is correct
4 Correct 4 ms 5248 KB Output is correct
5 Correct 4 ms 5248 KB Output is correct
6 Correct 4 ms 5248 KB Output is correct
7 Correct 4 ms 5248 KB Output is correct
8 Correct 5 ms 5248 KB Output is correct
9 Incorrect 4 ms 5248 KB Output isn't correct
10 Halted 0 ms 0 KB -