oj.uz

Submission #216718

# Submission time Handle Problem Language Result Execution time Memory
216718 2020-03-27T21:31:59 Z kimbj0709 Pipes (CEOI15_pipes) C++
80 / 100
 1430 ms 65536 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 4352 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 122 ms 7672 KB Output is correct
2 Correct 119 ms 7672 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 6648 KB Output is correct
2 Correct 222 ms 6140 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 7800 KB Output is correct
2 Correct 295 ms 6904 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 446 ms 10688 KB Output is correct
2 Correct 399 ms 7668 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 717 ms 11896 KB Output is correct
2 Correct 701 ms 9336 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 941 ms 13560 KB Output is correct
2 Correct 919 ms 9336 KB Output is correct

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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