oj.uz

Submission #375523

# Submission time Handle Problem Language Result Execution time Memory
375523 2021-03-09T13:38:20 Z ritul_kr_singh One-Way Streets (CEOI17_oneway) C++17
100 / 100
 147 ms 22248 KB 
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define sp << " " <<
#define nl << "\n"

vector<vector<pair<int, int>>> g0, g1;

vector<int> id, low, dfsNum, st;
int dfsTimer = 1;

void tarjan(int u, int parentEdge){
    dfsNum[u] = low[u] = dfsTimer++;
    st.push_back(u);
    for(auto e : g0[u]){
        if(e.second==parentEdge) continue;
        if(!dfsNum[e.first]) tarjan(e.first, e.second);
        low[u] = min(low[u], low[e.first]);
    }

    if(low[u]==dfsNum[u]){
        int v = -1;
        while(v!=u){
            v = st.back(); st.pop_back();
            id[v] = u;
        }
    }
}


int ans[100000] = {}, dir[100000] = {};
pair<int, int> edges[100000];

void dfs(int u){
    dfsNum[u] = -1;
    for(auto e : g1[u]){
        int v = e.first;
        if(dfsNum[v]<0) continue;
        dfs(v);
        dir[u] += dir[v];
        if(dir[v]==0) continue;
        if(dir[v]>0 == (id[edges[e.second].first]==u)) ans[e.second] = -1;
        else ans[e.second] = 1;
    }
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n, m; cin >> n >> m;

    g0.resize(n), g1.resize(n);
    for(int i=0; i<m; ++i){
        cin >> edges[i].first >> edges[i].second;
        --edges[i].first, --edges[i].second;
        if(edges[i].first == edges[i].second) continue;
        g0[edges[i].first].emplace_back(edges[i].second, i);
        g0[edges[i].second].emplace_back(edges[i].first, i);
    }
    dfsNum.assign(n, 0), id.assign(n, -1), low.resize(n);
    for(int i=0; i<n; ++i) if(!dfsNum[i]) tarjan(i, -1);

    for(int i=0; i<m; ++i){
        int x = id[edges[i].first], y = id[edges[i].second];
        if(x==y) continue;
        g1[x].emplace_back(y, i);
        g1[y].emplace_back(x, i);
    }

    int p; cin >> p;
    while(p--){
        int x, y; cin >> x >> y;
        x = id[x-1], y = id[y-1];
        ++dir[x]; // up
        --dir[y]; // down
    }

    for(int i=0; i<n; ++i) if(dfsNum[i]>=0) dfs(i);

    for(int i=0; i<m; ++i){
        char c = 'B';
        if(ans[i]<0) c = 'L';
        if(ans[i]>0) c = 'R';
        cout << c;
    }
}

Compilation message

oneway.cpp: In function 'void dfs(int)':
oneway.cpp:42:18: warning: suggest parentheses around comparison in operand of '==' [-Wparentheses]
   42 |         if(dir[v]>0 == (id[edges[e.second].first]==u)) ans[e.second] = -1;
      |            ~~~~~~^~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 43 ms 7276 KB Output is correct
12 Correct 50 ms 8684 KB Output is correct
13 Correct 68 ms 10904 KB Output is correct
14 Correct 95 ms 13732 KB Output is correct
15 Correct 91 ms 14584 KB Output is correct
16 Correct 98 ms 16236 KB Output is correct
17 Correct 96 ms 17948 KB Output is correct
18 Correct 104 ms 16492 KB Output is correct
19 Correct 96 ms 19180 KB Output is correct
20 Correct 68 ms 9444 KB Output is correct
21 Correct 48 ms 9704 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 43 ms 7276 KB Output is correct
12 Correct 50 ms 8684 KB Output is correct
13 Correct 68 ms 10904 KB Output is correct
14 Correct 95 ms 13732 KB Output is correct
15 Correct 91 ms 14584 KB Output is correct
16 Correct 98 ms 16236 KB Output is correct
17 Correct 96 ms 17948 KB Output is correct
18 Correct 104 ms 16492 KB Output is correct
19 Correct 96 ms 19180 KB Output is correct
20 Correct 68 ms 9444 KB Output is correct
21 Correct 48 ms 9704 KB Output is correct
22 Correct 115 ms 19180 KB Output is correct
23 Correct 122 ms 17564 KB Output is correct
24 Correct 147 ms 17644 KB Output is correct
25 Correct 116 ms 22248 KB Output is correct
26 Correct 113 ms 18656 KB Output is correct
27 Correct 112 ms 17516 KB Output is correct
28 Correct 50 ms 4460 KB Output is correct
29 Correct 66 ms 10220 KB Output is correct
30 Correct 66 ms 10728 KB Output is correct
31 Correct 73 ms 10608 KB Output is correct
32 Correct 75 ms 14240 KB Output is correct