oj.uz

답안 #216717

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
216717 2020-03-27T21:31:01 Z kimbj0709 Pipes (CEOI15_pipes) C++11
40 / 100
 1443 ms 50520 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

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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 124 ms 5880 KB Output is correct
2 Correct 117 ms 5880 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 197 ms 5752 KB Output is correct
2 Correct 241 ms 5368 KB Output is correct

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 334 ms 7032 KB Output is correct
2 Runtime error 309 ms 19912 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 460 ms 10488 KB Output is correct
2 Runtime error 408 ms 25720 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 714 ms 11512 KB Output is correct
2 Runtime error 720 ms 42348 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 933 ms 13232 KB Output is correct
2 Runtime error 910 ms 50520 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1156 ms 16748 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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1443 ms 29196 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -