oj.uz

답안 #1116119

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1116119 2024-11-21T09:19:36 Z noyancanturk Pipes (CEOI15_pipes) C++17
100 / 100
 1954 ms 13912 KB 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back

const int lim=1e5+1;

int parent[lim];
int find(int i){
  if(i==parent[i])return i;
  return parent[i]=find(parent[i]);
}
void unite(int i,int j){
  i=find(i),j=find(j);
  parent[i]=j;
}

struct vec{
  int*targ=new int[2],size=2,have=0;
  void pb(int t){
    if(have==size){
      int*newy=new int[int(size*1.5)];
      for(int i=0;i<size;i++)newy[i]=targ[i];
      size*=1.5;
      delete targ;
      targ=newy;
    }
    targ[have++]=t;
  }
  void clear(){
    have=0;
    size=2;
    delete targ;
    targ=new int[2];
  }
};

vec v[lim];
vector<pair<int,int>>edges;

int tin[lim],tout[lim],tt=1;

int dfs(int node,int par){
  if(tin[node])return tin[node];
  tout[node]=tin[node]=tt++;
  for(int i=0;i<v[node].have;i++){
    int j=v[node].targ[i];
    if(j==par)continue;
    if(tin[j]){
      tout[node]=min(tout[node],tin[j]);
      unite(node,j);
    }else{
      int res=dfs(j,node);
      if(res<=tin[node]){
        unite(node,j);
      }
      tout[node]=min(tout[node],res);
    }
  }
  return tout[node];
}

int n,m;
void findans(){
  for(int i=0;i<=n;i++)v[i].clear();
  for(auto[x,y]:edges){
    v[find(x)].pb(find(y));
    v[find(y)].pb(find(x));
  }
  for(int i=0;i<=n;i++){
    tout[i]=tin[i]=0;
  }
  tt=1;
  for(int i=1;i<=n;i++){
    if(!tin[i])dfs(i,0);
  }
  for(int i=0;i<edges.size();i++){
    if(find(edges[i].first)==find(edges[i].second)){
      swap(edges[i],edges.back());
      edges.pop_back();
      i--;
    }
  }
}

int main(){
  cin>>n>>m;
  for(int i=1;i<=n;i++)parent[i]=i;
  for(int i=0;i<m;i++){
    int x,y;
    cin>>x>>y;
    if(find(x)!=find(y))edges.pb({x,y});
    if(edges.size()==150000)findans();
  }
  findans();
  for(auto[x,y]:edges)cout<<x<<' '<<y<<'\n';
}

Compilation message

pipes.cpp: In function 'void findans()':
pipes.cpp:76:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |   for(int i=0;i<edges.size();i++){
      |               ~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5712 KB Output is correct
2 Correct 7 ms 5712 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 6224 KB Output is correct
2 Correct 9 ms 5968 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 171 ms 9476 KB Output is correct
2 Correct 181 ms 9408 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 298 ms 9920 KB Output is correct
2 Correct 369 ms 9408 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 564 ms 10788 KB Output is correct
2 Correct 408 ms 10432 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 772 ms 13852 KB Output is correct
2 Correct 623 ms 10440 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 993 ms 13912 KB Output is correct
2 Correct 1033 ms 11748 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1253 ms 13332 KB Output is correct
2 Correct 1160 ms 10292 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1583 ms 13316 KB Output is correct
2 Correct 1567 ms 10176 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1954 ms 13248 KB Output is correct
2 Correct 1897 ms 12992 KB Output is correct