Submission #771516

#	Time	Username	Problem	Language	Result	Execution time	Memory
771516		peteza	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	39 ms	12832 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

int n, m, a, b, c;
int v1[100005], v2[100005];
bool vis[100005], visedge[100005];
char ans[100005];
vector<pii> adj[100005];
pii edges[100005];

void dfs(int x, int ass=-1) {
    vis[x] = 1;
    for(auto e:adj[x]) {
        if(visedge[e.second]) continue;
        visedge[e.second] = 1;
        if(vis[e.first]) {
            ans[e.second] = 'B';
            v1[x]++; v1[e.first]--;
        } else {
            dfs(e.first, e.second);
            v1[x] += v1[e.first];
            v2[x] += v2[e.first];
        }
    }
    if(!(~ass)) return;
    if(v1[x]) ans[ass] = 'B';
    else {
        if(!v2[x]) ans[ass] = 'B';
        else {
            ans[ass] = (((edges[ass].first == x) ^ (v2[x] > 0)) ? 'L' : 'R');
        }
    }
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> m;
    for(int i=0;i<m;i++) {
        cin >> a >> b;
        edges[i] = {a, b};
        adj[a].emplace_back(b, i);
        adj[b].emplace_back(a, i);
    }
    cin >> c;
    while(c--) {
        cin >> a >> b;
        v2[a]++; v2[b]--;
    }
    for(int i=1;i<=n;i++) if(!vis[i]) dfs(i);
    cout << ans;
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40