oj.uz

Submission #631685

# Submission time Handle Problem Language Result Execution time Memory
631685 2022-08-18T12:18:42 Z NintsiChkhaidze One-Way Streets (CEOI17_oneway) C++14
30 / 100
 825 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 bridge[N],vis[N];
map <int,bool> O[N],C[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++;
                
                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++;

                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:18:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   18 |     for (auto [to,id]: v[x]){
      |               ^
oneway.cpp: In function 'void dfs1(int)':
oneway.cpp:36:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |     for (auto [to,id]: v[x]){
      |               ^
oneway.cpp: In function 'int main()':
oneway.cpp:72: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]
   72 |         for (int j = 1; j < v[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~
oneway.cpp:86:25: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   86 |         vis[i] = tin[i] = 0;
      |                  ~~~~~~~^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16724 KB Output is correct
2 Correct 9 ms 16724 KB Output is correct
3 Correct 9 ms 16852 KB Output is correct
4 Correct 10 ms 17364 KB Output is correct
5 Correct 51 ms 26328 KB Output is correct
6 Correct 9 ms 16852 KB Output is correct
7 Correct 43 ms 26224 KB Output is correct
8 Correct 43 ms 26164 KB Output is correct
9 Correct 10 ms 16852 KB Output is correct
10 Correct 16 ms 17620 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16724 KB Output is correct
2 Correct 9 ms 16724 KB Output is correct
3 Correct 9 ms 16852 KB Output is correct
4 Correct 10 ms 17364 KB Output is correct
5 Correct 51 ms 26328 KB Output is correct
6 Correct 9 ms 16852 KB Output is correct
7 Correct 43 ms 26224 KB Output is correct
8 Correct 43 ms 26164 KB Output is correct
9 Correct 10 ms 16852 KB Output is correct
10 Correct 16 ms 17620 KB Output is correct
11 Correct 41 ms 21824 KB Output is correct
12 Correct 62 ms 25196 KB Output is correct
13 Correct 186 ms 60332 KB Output is correct
14 Correct 825 ms 227164 KB Output is correct
15 Runtime error 602 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16724 KB Output is correct
2 Correct 9 ms 16724 KB Output is correct
3 Correct 9 ms 16852 KB Output is correct
4 Correct 10 ms 17364 KB Output is correct
5 Correct 51 ms 26328 KB Output is correct
6 Correct 9 ms 16852 KB Output is correct
7 Correct 43 ms 26224 KB Output is correct
8 Correct 43 ms 26164 KB Output is correct
9 Correct 10 ms 16852 KB Output is correct
10 Correct 16 ms 17620 KB Output is correct
11 Correct 41 ms 21824 KB Output is correct
12 Correct 62 ms 25196 KB Output is correct
13 Correct 186 ms 60332 KB Output is correct
14 Correct 825 ms 227164 KB Output is correct
15 Runtime error 602 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -