oj.uz

Submission #259185

# Submission time Handle Problem Language Result Execution time Memory
259185 2020-08-07T10:39:07 Z dolphingarlic One-Way Streets (CEOI17_oneway) C++14
0 / 100
 3000 ms 5120 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 = find(1), int parent = 0) {
    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, ll val) {
    for (; pos <= timer; pos += (pos & (-pos))) bit[pos] += val;
}
int query(int pos) {
    int ans = 0;
    for (; pos; pos -= (pos & (-pos))) ans += bit[pos];
    return ans;
}

void dir_dfs(int node = find(1), int parent = 0) {
    for (pair<int, int> i : compressed[node]) if (i.first != parent) {
        int weight = query(tin[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 = 1;
    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 = 1;
    lca_dfs();

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

    dir_dfs();
    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 Execution timed out 3088 ms 5120 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3088 ms 5120 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3088 ms 5120 KB Time limit exceeded
2 Halted 0 ms 0 KB -