oj.uz

Submission #1015955

# Submission time Handle Problem Language Result Execution time Memory
1015955 2024-07-07T06:36:33 Z gyg One-Way Streets (CEOI17_oneway) C++17
30 / 100
 1536 ms 656 KB 
#pragma GCC optimize("O3", "unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int MAX_N = 1e3 + 5, MAX_M = 1e3 + 5, MAX_P = 1e2 + 5;

int n, m;
array<pii, MAX_M> edge;
array<unordered_multiset<int>, MAX_N> adj;
int p;
array<pii, MAX_P> path;

bitset<MAX_N> seen;
void dfs(int u) {
    seen[u] = true;
    for (int v : adj[u])
        if (!seen[v]) dfs(v);
}

array<char, MAX_M> ans;

int main() {
    // freopen("way.in", "r", stdin);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        edge[i] = {u, v};
        adj[u].insert(v), adj[v].insert(u);
    }

    cin >> p;
    for (int i = 1; i <= p; i++) cin >> path[i].first >> path[i].second;

    fill(ans.begin(), ans.end(), 'B');
    for (int i = 1; i <= m; i++) {
        int u = edge[i].first, v = edge[i].second;

        adj[v].erase(adj[v].find(u));
        for (int j = 1; j <= p; j++) {
            int s = path[j].first, f = path[j].second;
            seen &= 0, dfs(s);
            if (!seen[f]) ans[i] = 'L';
        }
        adj[v].insert(u);

        adj[u].erase(adj[u].find(v));
        for (int j = 1; j <= p; j++) {
            int s = path[j].first, f = path[j].second;
            seen &= 0, dfs(s);
            if (!seen[f]) ans[i] = 'R';
        }
        adj[u].insert(v);
    }

    for (int i = 1; i <= m; i++) cout << ans[i];
    cout << '\n';
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 173 ms 604 KB Output is correct
4 Correct 62 ms 600 KB Output is correct
5 Correct 1355 ms 604 KB Output is correct
6 Correct 869 ms 600 KB Output is correct
7 Correct 1536 ms 656 KB Output is correct
8 Correct 1155 ms 652 KB Output is correct
9 Correct 1431 ms 604 KB Output is correct
10 Correct 970 ms 604 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 173 ms 604 KB Output is correct
4 Correct 62 ms 600 KB Output is correct
5 Correct 1355 ms 604 KB Output is correct
6 Correct 869 ms 600 KB Output is correct
7 Correct 1536 ms 656 KB Output is correct
8 Correct 1155 ms 652 KB Output is correct
9 Correct 1431 ms 604 KB Output is correct
10 Correct 970 ms 604 KB Output is correct
11 Runtime error 1 ms 604 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 173 ms 604 KB Output is correct
4 Correct 62 ms 600 KB Output is correct
5 Correct 1355 ms 604 KB Output is correct
6 Correct 869 ms 600 KB Output is correct
7 Correct 1536 ms 656 KB Output is correct
8 Correct 1155 ms 652 KB Output is correct
9 Correct 1431 ms 604 KB Output is correct
10 Correct 970 ms 604 KB Output is correct
11 Runtime error 1 ms 604 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -