oj.uz

답안 #631198

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -