oj.uz

Submission #631648

# Submission time Handle Problem Language Result Execution time Memory
631648 2022-08-18T11:26:09 Z NintsiChkhaidze One-Way Streets (CEOI17_oneway) C++14
0 / 100
 832 ms 262144 KB 
#include <bits/stdc++.h>
#define s second
#define f first
#define pb push_back
using namespace std;
 
const int N = 100005;
vector <pair<int,int> > v[N];
int tin[N],low[N],a[N],b[N],ID[N],idx,cnt,dp[N];
vector <int> adj[N],vec[N],O[N],C[N];
set <int> open[N],close[N];
bool bridge[N],vis[N];
 
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 fill(int x){
    for (int y: O[x]){
        if (close[x].find(y) == close[x].end()) 
            open[x].insert(y);
        else close[x].erase(close[x].find(y));
    }
 
    for (int y: C[x]){
        if (open[x].find(y) == open[x].end()) 
            close[x].insert(y);
        else open[x].erase(open[x].find(y));
    }
    
}
 
void dfs2(int x,int par){
    vis[x] = 1;
    dp[x] = dp[par] + 1;
    fill(x);
    
    for (int to: adj[x]){
        if(to == par) continue;
        dfs2(to,x);
 
        for (int y: open[to]){
            if (close[x].find(y) == close[x].end()) 
                open[x].insert(y);
            else close[x].erase(close[x].find(y));
        }
 
        for (int y: close[to]){
            if (open[x].find(y) == open[x].end()) 
                close[x].insert(y);
            else open[x].erase(open[x].find(y));
        }
    }
}
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++) 
        vis[i] = 0;
 
    idx = 0;
    for (int i = 1; i <= n; i++){
        if (vis[i]) continue;
        idx++;
        dfs1(i);
    }
 
    for (int i = 1; i <= n; i++)
        for (int x: vec[i]){
            adj[i].pb(ID[x]);
            adj[ID[x]].pb(i);
        }
    
    int k;
    cin>>k;
    for (int i = 1; i <= k; i++){
        int x,y;
        cin>>x>>y;
        O[ID[x]].pb(i);
        C[ID[y]].pb(i);
    }

    for (int i = 1; i <= n; i++) 
        vis[i] = 0;
 
    for (int i = 1; i <= n; i++)
        if (!vis[i]) dfs2(i,i);
    
    for (int i = 1; i <= m; i++){
        if (bridge[i] == 0) cout<<'B';
        else{
            int x = ID[a[i]],y = ID[b[i]],o,c;
            if (dp[x] > dp[y]){
                o = open[x].size(),c = close[x].size();
                if(o && !c) cout<<'R';
                else if (!o && c) cout<<'L';
                else cout<<'B';
            }else{
                o = open[y].size(),c = close[y].size();
                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:34:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |     for (auto [to,id]: v[x]){
      |               ^

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21460 KB Output is correct
2 Correct 13 ms 21460 KB Output is correct
3 Correct 11 ms 21568 KB Output is correct
4 Correct 11 ms 21588 KB Output is correct
5 Correct 15 ms 23112 KB Output is correct
6 Correct 11 ms 21516 KB Output is correct
7 Correct 14 ms 22536 KB Output is correct
8 Correct 12 ms 21588 KB Output is correct
9 Runtime error 832 ms 262144 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21460 KB Output is correct
2 Correct 13 ms 21460 KB Output is correct
3 Correct 11 ms 21568 KB Output is correct
4 Correct 11 ms 21588 KB Output is correct
5 Correct 15 ms 23112 KB Output is correct
6 Correct 11 ms 21516 KB Output is correct
7 Correct 14 ms 22536 KB Output is correct
8 Correct 12 ms 21588 KB Output is correct
9 Runtime error 832 ms 262144 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 21460 KB Output is correct
2 Correct 13 ms 21460 KB Output is correct
3 Correct 11 ms 21568 KB Output is correct
4 Correct 11 ms 21588 KB Output is correct
5 Correct 15 ms 23112 KB Output is correct
6 Correct 11 ms 21516 KB Output is correct
7 Correct 14 ms 22536 KB Output is correct
8 Correct 12 ms 21588 KB Output is correct
9 Runtime error 832 ms 262144 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -