oj.uz

Submission #1116096

# Submission time Handle Problem Language Result Execution time Memory
1116096 2024-11-21T09:02:03 Z vjudge1 Pipes (CEOI15_pipes) C++17
10 / 100
 2177 ms 65536 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[5],size=5,have=0;
  void pb(int t){
    if(have==size){
      int*newy=new int[size*2];
      for(int i=0;i<size;i++)newy[i]=targ[i];
      size*=2;
      delete targ;
      targ=newy;
    }
    targ[have++]=t;
  }
  void clear(){
    have=0;
    delete targ;
  }
};

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

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

int dfs(int node,int par){
  if(tout[node])return tout[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;
    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(auto[x,y]:edges){
    v[find(x)].pb(find(y));
    v[find(y)].pb(find(x));
  }
  for(int i=1;i<=n;i++){
    tout[i]=tin[i]=0;
  }
  tt=1;
  for(int i=1;i<=n;i++){
    if(!tout[i])dfs(i,0);
  }
  vector<pair<int,int>>edges1;
  for(auto[x,y]:edges){
    if(find(x)!=find(y))edges1.pb({x,y});
  }
  edges=edges1;
}

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()==200000)findans();
  }
  findans();
  for(auto[x,y]:edges)cout<<x<<' '<<y<<'\n';
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5712 KB Output is correct
2 Incorrect 4 ms 5712 KB Wrong number of edges
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6220 KB Output is correct
2 Incorrect 9 ms 5872 KB Wrong number of edges
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 10332 KB Output is correct
2 Incorrect 173 ms 10176 KB Wrong number of edges
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 11000 KB Output is correct
2 Incorrect 346 ms 10624 KB Wrong number of edges
3 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 11712 KB Output is correct
2 Correct 440 ms 11472 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 652 ms 14784 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 973 ms 16632 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1327 ms 59328 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1689 ms 65536 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2177 ms 65536 KB Memory limit exceeded
2 Halted 0 ms 0 KB -