oj.uz

Submission #216720

# Submission time Handle Problem Language Result Execution time Memory
216720 2020-03-27T21:34:19 Z kimbj0709 Pipes (CEOI15_pipes) C++
100 / 100
 1316 ms 14588 KB 
#include<bits/stdc++.h>
using namespace std;
#define maxn 100050
int ufds[2][maxn];
inline int find(int a,int b){
  if(ufds[a][b]!=b){
    ufds[a][b] = find(a,ufds[a][b]);
  }
  return ufds[a][b];
}
void merge(int a,int b,int c){
  int temp1 = find(a,b);
  int temp2 = find(a,c);
  ufds[a][min(temp1,temp2)] = max(temp1,temp2);
}
vector<vector<int> > adj(maxn);
vector<int> level(maxn,-1);
vector<int> low(maxn);
int t = 1;
void dfs(int node,int parent){
  level[node] = t;
  low[node] = t;
  t++;
  bool idk = 0;
  for(auto k:adj[node]){
    if(k==parent&&idk==0){
      idk = 1;
      continue;
    }
    if(level[k]!=-1){//visited
      low[node] = min(low[node],level[k]);
    }
    else{
      dfs(k,node);
      if(level[node]<low[k]){
        cout << k << " " << node << "\n";
      }
      low[node] = min(low[node],low[k]);
    }
  }
}
int32_t main(){
  ios::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);
  int no_of_vertex,no_of_edge;
  int input1,input2;
  cin >> no_of_vertex >> no_of_edge;
  for(int i=0;i<maxn;i++){
    ufds[0][i] = i;
    ufds[1][i] = i;
  }
  for(int i=0;i<no_of_edge;i++){
    cin >> input1 >> input2;
    if(find(0,input1)!=find(0,input2)){
      merge(0,input1,input2);
      adj[input1].push_back(input2);
      adj[input2].push_back(input1);
      continue;
    }
    if(find(1,input1)!=find(1,input2)){
      merge(1,input1,input2);
      adj[input1].push_back(input2);
      adj[input2].push_back(input1);
      continue;
    }
  }
  for(int i=1;i<=no_of_vertex;i++){
    if(level[i]==-1){
      dfs(i,-1);
    }
  }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4224 KB Output is correct
2 Correct 7 ms 4224 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4736 KB Output is correct
2 Correct 11 ms 4608 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 6264 KB Output is correct
2 Correct 111 ms 6020 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 6392 KB Output is correct
2 Correct 211 ms 5752 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 7416 KB Output is correct
2 Correct 274 ms 6940 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 450 ms 10872 KB Output is correct
2 Correct 375 ms 7928 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 664 ms 12152 KB Output is correct
2 Correct 671 ms 9808 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 887 ms 14016 KB Output is correct
2 Correct 847 ms 9720 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1097 ms 14588 KB Output is correct
2 Correct 1051 ms 9592 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1316 ms 13836 KB Output is correct
2 Correct 1269 ms 10488 KB Output is correct