oj.uz

Submission #631203

# Submission time Handle Problem Language Result Execution time Memory
631203 2022-08-17T19:53:40 Z NintsiChkhaidze One-Way Streets (CEOI17_oneway) C++14
0 / 100
 4 ms 7380 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];
vector <int> open[N],close[N];
bool bridge[N],vis[N],F[N];
pair<int,int> res[N];
vector <int> vec;
int f[N],o,c,cnt;

void dfs(int x,int par){
    f[x] = 1;
    tin[x] = low[x] = cnt++;
    for (auto [to,id]: v[x]){
        if (to == par) continue;
        if (f[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 DFS(int x){
    vis[x] = 1;
    for (int y: open[x]){
        o++;
        f[y]++;
        if (f[y] == 0) o--,c--;
    }

    for (int y: close[x]){
        c++;
        f[y]--;
        if (f[y] == 0) o--,c--;
    }

    for (auto [to,id]: v[x])
        if (!vis[to] && !bridge[id]) DFS(to);

    for (auto [to,id]: v[x])
        if (bridge[id]) vec.pb(x);
}

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 (!f[i]) dfs(i,i); 

    int k;
    cin>>k;
    for (int i = 1; i <= k; i++){
        int x,y;
        cin>>x>>y;
        open[x].pb(i);
        close[y].pb(i);
    }

    for (int i = 1; i <= n; i++){
        if(!vis[i]) {
            for (int j =1 ; j <= k; j++) f[j]=0;
            vec.clear();
            o=c=0;
            DFS(i);
            for (int x: vec)
                res[x] = {o,c};
        }
    }
        
    for (int i = 1; i <= m; i++){
        if (bridge[i] == 0) cout<<'B';
        else{
            o = res[a[i]].f,c=res[a[i]].s;
            if(o && !c) cout<<'R';
            else if (!o && c) cout<<'L';
            else cout<<'B';
        }
    }

}

Compilation message

oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:19:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   19 |     for (auto [to,id]: v[x]){
      |               ^
oneway.cpp: In function 'void DFS(int)':
oneway.cpp:46:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   46 |     for (auto [to,id]: v[x])
      |               ^
oneway.cpp:49:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |     for (auto [to,id]: v[x])
      |               ^

Subtask #1
0 / 30.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 40.0

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