oj.uz

Submission #595759

# Submission time Handle Problem Language Result Execution time Memory
595759 2022-07-14T06:11:59 Z 1bin One-Way Streets (CEOI17_oneway) C++14
100 / 100
 122 ms 23556 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 1e5 + 5;
int n, m, P, a[NMAX], b[NMAX], u, v, vis[NMAX];
int dfsn[NMAX], low[NMAX], t, cl[NMAX], ans[NMAX], chk[NMAX], f[NMAX];
vector<pair<int, int>> adj[NMAX], g[NMAX];
 
void dfs(int x, int e){
    dfsn[x] = low[x] = ++t;
    for(auto& [nx, ix] : adj[x]){
        if(ix == e) continue;
        if(!dfsn[nx]){
            dfs(nx, ix);
            low[x] = min(low[x], low[nx]);
        }
        else if(dfsn[nx] < dfsn[x]) low[x] = min(low[x], dfsn[nx]);
    }
    return;
}
 
void dfs2(int x, int c){
    cl[x] = c;
    for(auto& [nx, ix] : adj[x]){
        if(cl[nx]) continue;
        if(low[nx] > dfsn[x]) {
            g[c].emplace_back(++t, ix);
            g[t].emplace_back(c, ix);
            dfs2(nx, t);
        }
        else dfs2(nx, c);
    }
    return;
}
 
void dfs3(int x){
    vis[x] = 1;
    for(auto& [nx, ix] : g[x]){
        if(vis[nx]) continue;
        dfs3(nx);
        if(chk[nx]){
            if(chk[nx] > 0 && nx == cl[a[ix]] || chk[nx] < 0 && x == cl[a[ix]]) ans[ix] = 1;
            else ans[ix] = -1;
        }
        chk[x] += chk[nx];
    }
    return;
}
 
int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> a[i] >> b[i];
        f[i] = 1;
        adj[a[i]].emplace_back(b[i], i);
        adj[b[i]].emplace_back(a[i], i);
    }
    
    for(int i = 1; i <= n; i++)
        if(!dfsn[i]) dfs(i, -1);
    t = 0;
    for(int i = 1; i <= n; i++)
        if(!cl[i]) dfs2(i, ++t);
        
    cin >> P;
    while(P--){
        cin >> u >> v;
        chk[cl[u]]++; chk[cl[v]]--;
    }
    
    for(int i = 1; i <= t; i++)
        if(!vis[i]) dfs3(i);
        
    for(int i = 0; i < m; i++){
        if(!ans[i]) cout << 'B';
        else cout << (ans[i] > 0 ? 'R' : 'L');
    }
    return 0;
}

Compilation message

oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:14:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   14 |     for(auto& [nx, ix] : adj[x]){
      |               ^
oneway.cpp: In function 'void dfs2(int, int)':
oneway.cpp:27:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   27 |     for(auto& [nx, ix] : adj[x]){
      |               ^
oneway.cpp: In function 'void dfs3(int)':
oneway.cpp:41:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |     for(auto& [nx, ix] : g[x]){
      |               ^
oneway.cpp:45:28: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   45 |             if(chk[nx] > 0 && nx == cl[a[ix]] || chk[nx] < 0 && x == cl[a[ix]]) ans[ix] = 1;
      |                ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 4 ms 5076 KB Output is correct
5 Correct 3 ms 5168 KB Output is correct
6 Correct 3 ms 5036 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 5036 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 4 ms 5076 KB Output is correct
5 Correct 3 ms 5168 KB Output is correct
6 Correct 3 ms 5036 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 5036 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 39 ms 11700 KB Output is correct
12 Correct 39 ms 12712 KB Output is correct
13 Correct 58 ms 14012 KB Output is correct
14 Correct 67 ms 15600 KB Output is correct
15 Correct 66 ms 15992 KB Output is correct
16 Correct 73 ms 16844 KB Output is correct
17 Correct 64 ms 18876 KB Output is correct
18 Correct 91 ms 17228 KB Output is correct
19 Correct 61 ms 20280 KB Output is correct
20 Correct 44 ms 12272 KB Output is correct
21 Correct 45 ms 12412 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 4 ms 5076 KB Output is correct
5 Correct 3 ms 5168 KB Output is correct
6 Correct 3 ms 5036 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 5036 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 39 ms 11700 KB Output is correct
12 Correct 39 ms 12712 KB Output is correct
13 Correct 58 ms 14012 KB Output is correct
14 Correct 67 ms 15600 KB Output is correct
15 Correct 66 ms 15992 KB Output is correct
16 Correct 73 ms 16844 KB Output is correct
17 Correct 64 ms 18876 KB Output is correct
18 Correct 91 ms 17228 KB Output is correct
19 Correct 61 ms 20280 KB Output is correct
20 Correct 44 ms 12272 KB Output is correct
21 Correct 45 ms 12412 KB Output is correct
22 Correct 83 ms 20028 KB Output is correct
23 Correct 103 ms 18172 KB Output is correct
24 Correct 122 ms 18368 KB Output is correct
25 Correct 76 ms 23556 KB Output is correct
26 Correct 85 ms 19516 KB Output is correct
27 Correct 76 ms 18252 KB Output is correct
28 Correct 31 ms 9476 KB Output is correct
29 Correct 67 ms 13000 KB Output is correct
30 Correct 53 ms 13372 KB Output is correct
31 Correct 54 ms 13480 KB Output is correct
32 Correct 59 ms 17184 KB Output is correct