Submission #1015955

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015955		gyg	One-Way Streets (CEOI17_oneway)	C++17	30 / 100	1536 ms	656 KiB

oneway

#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 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40