oj.uz

Submission #216719

# Submission time Handle Problem Language Result Execution time Memory
216719 2020-03-27T21:32:46 Z kimbj0709 Pipes (CEOI15_pipes) C++14
80 / 100
 1434 ms 22520 KB 
#include<bits/stdc++.h>
using namespace std;
#define maxn 100050
int ufds[2][maxn];
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 10 ms 4608 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 8440 KB Output is correct
2 Correct 114 ms 8312 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 7928 KB Output is correct
2 Correct 243 ms 6760 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 8440 KB Output is correct
2 Correct 300 ms 7672 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 10832 KB Output is correct
2 Correct 395 ms 7800 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 718 ms 12024 KB Output is correct
2 Correct 703 ms 9592 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 953 ms 13944 KB Output is correct
2 Correct 904 ms 9592 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1171 ms 16676 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1434 ms 13816 KB Output is correct
2 Runtime error 1388 ms 22520 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)