oj.uz

Submission #631198

# Submission time Handle Problem Language Result Execution time Memory
631198 2022-08-17T19:36:40 Z NintsiChkhaidze One-Way Streets (CEOI17_oneway) C++14
30 / 100
 3000 ms 15540 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];
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) c--,o--;
    }

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

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 <= m; i++){
        if (bridge[i] == 0) cout<<'B';
        else{
            o = 0,c=0;
            for (int j=1;j<=k;j++) f[j] = 0;
            for (int j=1;j<=n;j++) vis[j] = 0;
            F[i] = 1;
            DFS(a[i]);
            F[i] = 0;
            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: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 DFS(int)':
oneway.cpp:44:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   44 |     for (auto [to,id]: v[x])
      |               ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7388 KB Output is correct
2 Correct 3 ms 7380 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 15 ms 7476 KB Output is correct
5 Correct 14 ms 7392 KB Output is correct
6 Correct 5 ms 7380 KB Output is correct
7 Correct 14 ms 7512 KB Output is correct
8 Correct 13 ms 7508 KB Output is correct
9 Correct 5 ms 7380 KB Output is correct
10 Correct 5 ms 7380 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7388 KB Output is correct
2 Correct 3 ms 7380 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 15 ms 7476 KB Output is correct
5 Correct 14 ms 7392 KB Output is correct
6 Correct 5 ms 7380 KB Output is correct
7 Correct 14 ms 7512 KB Output is correct
8 Correct 13 ms 7508 KB Output is correct
9 Correct 5 ms 7380 KB Output is correct
10 Correct 5 ms 7380 KB Output is correct
11 Correct 35 ms 13460 KB Output is correct
12 Correct 341 ms 14624 KB Output is correct
13 Execution timed out 3043 ms 15540 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7388 KB Output is correct
2 Correct 3 ms 7380 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 15 ms 7476 KB Output is correct
5 Correct 14 ms 7392 KB Output is correct
6 Correct 5 ms 7380 KB Output is correct
7 Correct 14 ms 7512 KB Output is correct
8 Correct 13 ms 7508 KB Output is correct
9 Correct 5 ms 7380 KB Output is correct
10 Correct 5 ms 7380 KB Output is correct
11 Correct 35 ms 13460 KB Output is correct
12 Correct 341 ms 14624 KB Output is correct
13 Execution timed out 3043 ms 15540 KB Time limit exceeded
14 Halted 0 ms 0 KB -