oj.uz

Submission #1005960

# Submission time Handle Problem Language Result Execution time Memory
1005960 2024-06-23T09:12:06 Z SulA One-Way Streets (CEOI17_oneway) C++17
100 / 100
 282 ms 40532 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5;

vector<int> adj[MAXN+1];
map<pair<int,int>, int> edge;
map<pair<int,int>, char> ans;
map<pair<int,int>, bool> fir;
int dep[MAXN+1], low[MAXN+1], cntX[MAXN+1], cntY[MAXN+1];

void dfs(int v, int p) {
    dep[v] = low[v] = dep[p] + 1;
    for (int u : adj[v]) {
        if (u == p || u == v) continue;
        if (dep[u] == 0) {
            dfs(u, v);
            low[v] = min(low[v], low[u]);
            cntX[v] += cntX[u];
            cntY[v] += cntY[u];
        } else {
            low[v] = min(low[v], dep[u]);
        }
    }

    if (cntX[v] == cntY[v] || dep[v] != low[v] || edge[{p,v}] + edge[{v,p}] != 1) return;
    int node1 = v, node2 = p;
    if (fir.find({v, p}) == fir.end()) swap(node1, node2);
    pair<int,int> orient;
    if (cntX[v] > cntY[v]) {
        // edge should go from v -> p
        orient = {v, p};
    } else {
        orient = {p, v};
    }

    if (orient == make_pair(node1, node2)) {
        ans[{node1, node2}] = 'R';
    } else {
        ans[{node1, node2}] = 'L';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n,m; cin >> n >> m;
    pair<int,int> graph[m];
    for (int i = 0; i < m; i++) {
        int a,b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
        edge[{a,b}]++;
        graph[i] = {a, b};
        fir[{a,b}] = true;
    }
    int p; cin >> p;
    while (p--) {
        int x,y; cin >> x >> y;
        cntX[x]++, cntY[y]++;
    }

    for (int v = 1; v <= n; v++) {
        if (dep[v] == 0) {
            dfs(v,0);
        }
    }
    for (auto [a,b] : graph) {
        cout << (ans[{a,b}] == 0 ? 'B' : ans[{a,b}]);
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4184 KB Output is correct
2 Correct 1 ms 3964 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 3 ms 4440 KB Output is correct
6 Correct 1 ms 4188 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 2 ms 4188 KB Output is correct
10 Correct 2 ms 4188 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4184 KB Output is correct
2 Correct 1 ms 3964 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 3 ms 4440 KB Output is correct
6 Correct 1 ms 4188 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 2 ms 4188 KB Output is correct
10 Correct 2 ms 4188 KB Output is correct
11 Correct 110 ms 27400 KB Output is correct
12 Correct 108 ms 28496 KB Output is correct
13 Correct 125 ms 29780 KB Output is correct
14 Correct 112 ms 30096 KB Output is correct
15 Correct 118 ms 30108 KB Output is correct
16 Correct 118 ms 27216 KB Output is correct
17 Correct 148 ms 32352 KB Output is correct
18 Correct 121 ms 27220 KB Output is correct
19 Correct 177 ms 34040 KB Output is correct
20 Correct 108 ms 28008 KB Output is correct
21 Correct 113 ms 26876 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4184 KB Output is correct
2 Correct 1 ms 3964 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 3 ms 4440 KB Output is correct
6 Correct 1 ms 4188 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 2 ms 4188 KB Output is correct
10 Correct 2 ms 4188 KB Output is correct
11 Correct 110 ms 27400 KB Output is correct
12 Correct 108 ms 28496 KB Output is correct
13 Correct 125 ms 29780 KB Output is correct
14 Correct 112 ms 30096 KB Output is correct
15 Correct 118 ms 30108 KB Output is correct
16 Correct 118 ms 27216 KB Output is correct
17 Correct 148 ms 32352 KB Output is correct
18 Correct 121 ms 27220 KB Output is correct
19 Correct 177 ms 34040 KB Output is correct
20 Correct 108 ms 28008 KB Output is correct
21 Correct 113 ms 26876 KB Output is correct
22 Correct 262 ms 35668 KB Output is correct
23 Correct 221 ms 33112 KB Output is correct
24 Correct 282 ms 32948 KB Output is correct
25 Correct 222 ms 40532 KB Output is correct
26 Correct 221 ms 35156 KB Output is correct
27 Correct 227 ms 33104 KB Output is correct
28 Correct 52 ms 7764 KB Output is correct
29 Correct 125 ms 27320 KB Output is correct
30 Correct 128 ms 27472 KB Output is correct
31 Correct 128 ms 28076 KB Output is correct
32 Correct 137 ms 30548 KB Output is correct