oj.uz

Submission #631682

# Submission time Handle Problem Language Result Execution time Memory
631682 2022-08-18T12:16:53 Z NintsiChkhaidze One-Way Streets (CEOI17_oneway) C++14
60 / 100
 376 ms 262144 KB 
#include <bits/stdc++.h>
#define s second
#define f first
#define pb push_back
using namespace std;
 
const int N = 100005;
int tin[N],low[N],a[N],b[N],ID[N];
bool O[N][1005],C[N][1005],bridge[N],vis[N];
vector <int> adj[N],vec[N];
vector <pair<int,int> > v[N];
int k,idx,cnt;
 
void dfs(int x,int par){
    vis[x] = 1;
    tin[x] = low[x] = cnt++;
    for (auto [to,id]: v[x]){
        if (to == par) continue;

        if (vis[to]){
            low[x] = min(low[x], tin[to]);
        }else{
            dfs(to,x);
            low[x] = min(low[x], low[to]);
            if (low[to] > tin[x])
                bridge[id] = 1;
        }
    }
}
    
 
void dfs1(int x){
    ID[x] = idx;
    vis[x] = 1;
    for (auto [to,id]: v[x]){
        if (!vis[to] && !bridge[id]) dfs1(to);
        else if (!vis[to] && bridge[id]) vec[idx].pb(to);
    }
}
 
 
void dfs2(int x,int par){
    vis[x] = 1;
    tin[x] = tin[par] + 1;
    for (int to: adj[x]){
        if (vis[to]) continue;
        dfs2(to,x);
 
        for (int j = 1; j <= k; j++){
            O[x][j] |= O[to][j];
            C[x][j] |= C[to][j];
        }

    }
}
int main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    int n,m;
    cin>>n>>m;
    for (int i = 1; i <= m; i++){
        cin>>a[i]>>b[i];
        v[a[i]].pb({b[i],i});
        v[b[i]].pb({a[i],i});
    }

    for (int i= 1; i <= n; i++)
        if (!vis[i]) dfs(i,i); 

    for (int i = 1; i <= n; i++) {
        sort(v[i].begin(),v[i].end());
        for (int j = 1; j < v[i].size(); j++)
            if (v[i][j].f == v[i][j - 1].f){
                bridge[v[i][j].s] = bridge[v[i][j - 1].s] = 0;
            }
    }
    
    for (int i= 1; i <= n; i++) 
        vis[i] = 0;
 
    idx = 0;
    for (int i = 1; i <= n; i++)
        if (!vis[i]) idx++,dfs1(i);
    
    for (int i = 1; i <= n; i++) 
        vis[i] = tin[i] = 0;
 
    for (int i = 1; i <= n; i++)
        for (int x: vec[i]){
            adj[i].pb(ID[x]);
            adj[ID[x]].pb(i);
        }
    
    cin>>k;
    for (int i = 1; i <= k; i++){
        int x,y;
        cin>>x>>y;
        O[ID[x]][i] = C[ID[y]][i] = 1;
    }

    for (int i = 1; i <= n; i++)
        if (!vis[i]) dfs2(i,i);

    for (int i = 1; i <= m; i++){
        if (!bridge[i]) cout<<'B';
        else{
            int x = ID[a[i]],y = ID[b[i]],o=0,c=0;

            if (tin[x] >= tin[y]){
                for (int j = 1; j <= k; j++)
                    if (O[x][j] && !C[x][j]) o++;
                    else if (!O[x][j] && C[x][j]) c++;
                
                // cout<<o<<" * "<<c<<endl;
                if(o && !c) cout<<'R';
                else if (!o && c) cout<<'L';
                else cout<<'B';
            }else{
                for (int j = 1; j <= k; j++)
                    if (O[y][j] && !C[y][j]) o++;
                    else if (!O[y][j] && C[y][j]) c++;

                // cout<<o<<" & "<<c<<endl;
                if(o && !c) cout<<'L';
                else if (!o && c) cout<<'R';
                else cout<<'B';
            }
            
        }
    }
 
}

Compilation message

oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:17:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   17 |     for (auto [to,id]: v[x]){
      |               ^
oneway.cpp: In function 'void dfs1(int)':
oneway.cpp:35:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   35 |     for (auto [to,id]: v[x]){
      |               ^
oneway.cpp: In function 'int main()':
oneway.cpp:71:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for (int j = 1; j < v[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~
oneway.cpp:85:25: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   85 |         vis[i] = tin[i] = 0;
      |                  ~~~~~~~^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7568 KB Output is correct
4 Correct 5 ms 9428 KB Output is correct
5 Correct 5 ms 9456 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 5 ms 9508 KB Output is correct
8 Correct 5 ms 9300 KB Output is correct
9 Correct 4 ms 7444 KB Output is correct
10 Correct 4 ms 7636 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7568 KB Output is correct
4 Correct 5 ms 9428 KB Output is correct
5 Correct 5 ms 9456 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 5 ms 9508 KB Output is correct
8 Correct 5 ms 9300 KB Output is correct
9 Correct 4 ms 7444 KB Output is correct
10 Correct 4 ms 7636 KB Output is correct
11 Correct 52 ms 13540 KB Output is correct
12 Correct 51 ms 14540 KB Output is correct
13 Correct 55 ms 18132 KB Output is correct
14 Correct 86 ms 50764 KB Output is correct
15 Correct 105 ms 70220 KB Output is correct
16 Correct 187 ms 203224 KB Output is correct
17 Correct 223 ms 215980 KB Output is correct
18 Correct 249 ms 203516 KB Output is correct
19 Correct 216 ms 217356 KB Output is correct
20 Correct 56 ms 14100 KB Output is correct
21 Correct 51 ms 15820 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7568 KB Output is correct
4 Correct 5 ms 9428 KB Output is correct
5 Correct 5 ms 9456 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 5 ms 9508 KB Output is correct
8 Correct 5 ms 9300 KB Output is correct
9 Correct 4 ms 7444 KB Output is correct
10 Correct 4 ms 7636 KB Output is correct
11 Correct 52 ms 13540 KB Output is correct
12 Correct 51 ms 14540 KB Output is correct
13 Correct 55 ms 18132 KB Output is correct
14 Correct 86 ms 50764 KB Output is correct
15 Correct 105 ms 70220 KB Output is correct
16 Correct 187 ms 203224 KB Output is correct
17 Correct 223 ms 215980 KB Output is correct
18 Correct 249 ms 203516 KB Output is correct
19 Correct 216 ms 217356 KB Output is correct
20 Correct 56 ms 14100 KB Output is correct
21 Correct 51 ms 15820 KB Output is correct
22 Runtime error 376 ms 262144 KB Execution killed with signal 11
23 Halted 0 ms 0 KB -