oj.uz

Submission #488447

# Submission time Handle Problem Language Result Execution time Memory
488447 2021-11-19T00:03:00 Z SirCovidThe19th One-Way Streets (CEOI17_oneway) C++17
0 / 100
 1 ms 2572 KB 
#include <bits/stdc++.h>
using namespace std;

const int mx = 1e5 + 5;

int n, m, p, l[mx], r[mx], par[mx], in[mx], active[mx], actQry[mx], ans[mx]; 
vector<pair<int, int>> adj[mx]; 

void dfs(int cur){
    bool triedP = 0;
    for (auto [nxt, id] : adj[cur]){
        if (par[nxt] == cur) continue;
        if (nxt == par[cur] and !triedP){ triedP = 1; continue; }

        if (!par[nxt]){
            par[nxt] = cur; dfs(nxt); 
            active[cur] += active[nxt]; 
            if (!active[nxt]){
                int curL = (cur == l[id]) ? -1 : 1; 
                ans[id] = curL * actQry[nxt];
            }
            actQry[cur] += actQry[nxt];
        }
        else in[nxt]++, active[cur]++;
    }
    active[cur] -= in[cur];
}

int main(){
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        int a, b; cin >> a >> b; 
        l[i] = a; r[i] = b;
        adj[a].push_back({b, i}); adj[b].push_back({a, i});
    }
    cin >> p;
    for (int i = 1; i <= p; i++){
        int a, b; cin >> a >> b;
        actQry[a]++; actQry[b]--;
    }
    par[1] = -1; dfs(1);
    for (int i = 1; i <= m; i++) cout<<(!ans[i] ? "B" : (ans[i] == -1 ? "L" : "R"));
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2572 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2572 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2572 KB Output isn't correct
2 Halted 0 ms 0 KB -