Submission #216720

#	Time	Username	Problem	Language	Result	Execution time	Memory
216720		kimbj0709	Pipes (CEOI15_pipes)	C++98	100 / 100	1316 ms	14588 KiB

pipes

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10