oj.uz

Submission #872544

# Submission time Handle Problem Language Result Execution time Memory
872544 2023-11-13T10:48:13 Z vjudge1 One-Way Streets (CEOI17_oneway) C++17
30 / 100
 3000 ms 5848 KB 
//author: Ahmet Alp Orakci
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

struct Edge {
    int u, v;
};

#define ONLINE_JUDGE
void solve() {
    int n, m, p;
    cin >> n >> m;

    vector <pair <int, int>> adj[n +1];

    vector <Edge> edges(m);
    for(int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v;

        adj[edges[i].u].emplace_back(edges[i].v, i);
        adj[edges[i].v].emplace_back(edges[i].u, i);
    }
    
    cin >> p;
    vector <pair <int, int>> must(p);
    for(int i = 0; i < p; i++) {
        cin >> must[i].first >> must[i].second;
    }

    auto checkleft = [&](int num) -> bool {
        for(auto &[a, b] : must) {
            vector <bool> vis(n +1);
            queue <int> q;
            q.emplace(a);

            while(!q.empty()) {
                int node = q.front();
                q.pop();
                if(vis[node]) {
                    continue;
                }
                vis[node] = true;

                for(auto [child, edgnum] : adj[node]) {
                    if(edgnum == num) {
                        if(child == edges[edgnum].u) 
                            continue;
                        else
                            q.emplace(child);
                    } else {
                        if(!vis[child])
                            q.emplace(child);
                    }
                }
            }

            if(!vis[b]) {
                return false;
            }
        }

        return true;
    };

    auto checkright = [&](int num) -> bool {
        for(auto &[a, b] : must) {
            vector <bool> vis(n +1);
            queue <int> q;
            q.emplace(a);

            while(!q.empty()) {
                int node = q.front();
                q.pop();
                if(vis[node]) {
                    continue;
                }
                vis[node] = true;

                for(auto [child, edgnum] : adj[node]) {
                    if(edgnum == num) {
                        if(child == edges[edgnum].v) 
                            continue;
                        else
                            q.emplace(child);
                    } else {
                        if(!vis[child])
                            q.emplace(child);
                    }
                }
            }

            if(!vis[b]) {
                return false;
            }
        }

        return true;
    };

    for(int i = 0; i < m; i++) {
        bool res1 = checkleft(i), res2 = checkright(i);
        if(res1 && res2) {
            cout << "B";
        } else if(res1) {
            cout << "R";
        } else if(res2) {
            cout << "L";
        } else {
            cout << "X";
        }
    }
    
    return;
}

signed main() {
    #ifndef ONLINE_JUDGE
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int t = 1; //cin >> t;
    for(int i = 1; i <= t; i++) {
        solve();
    }

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 375 ms 348 KB Output is correct
4 Correct 108 ms 732 KB Output is correct
5 Correct 1630 ms 512 KB Output is correct
6 Correct 1631 ms 480 KB Output is correct
7 Correct 1879 ms 524 KB Output is correct
8 Correct 1717 ms 508 KB Output is correct
9 Correct 2738 ms 492 KB Output is correct
10 Correct 2231 ms 484 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 375 ms 348 KB Output is correct
4 Correct 108 ms 732 KB Output is correct
5 Correct 1630 ms 512 KB Output is correct
6 Correct 1631 ms 480 KB Output is correct
7 Correct 1879 ms 524 KB Output is correct
8 Correct 1717 ms 508 KB Output is correct
9 Correct 2738 ms 492 KB Output is correct
10 Correct 2231 ms 484 KB Output is correct
11 Execution timed out 3059 ms 5848 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 456 KB Output is correct
3 Correct 375 ms 348 KB Output is correct
4 Correct 108 ms 732 KB Output is correct
5 Correct 1630 ms 512 KB Output is correct
6 Correct 1631 ms 480 KB Output is correct
7 Correct 1879 ms 524 KB Output is correct
8 Correct 1717 ms 508 KB Output is correct
9 Correct 2738 ms 492 KB Output is correct
10 Correct 2231 ms 484 KB Output is correct
11 Execution timed out 3059 ms 5848 KB Time limit exceeded
12 Halted 0 ms 0 KB -