oj.uz

Submission #1059047

# Submission time Handle Problem Language Result Execution time Memory
1059047 2024-08-14T16:27:04 Z NemanjaSo2005 Pipes (CEOI15_pipes) C++17
20 / 100
 2238 ms 55460 KB 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;
int N,M,vel[maxn],rod[maxn],dub[maxn],lift[maxn][17],kol[maxn];
vector<int> stablo[maxn];
void dfs(int gde,int pret){
   //cout<<gde<<" "<<pret<<endl;
   dub[gde]=dub[pret]+1;
   lift[gde][0]=pret;
   for(int i=1;i<=16;i++)
      lift[gde][i]=lift[lift[gde][i-1]][i-1];
   for(int x:stablo[gde])
      if(x!=pret)
         dfs(x,gde);
}
inline int getp(int x){
   if(rod[x]==x)
      return x;
   rod[x]=getp(rod[x]);
   return rod[x];
}
inline void spoj(int a,int b){
   int oa=a,ob=b;
   a=getp(a);
   b=getp(b);
   //cout<<a<<" ab "<<b<<endl;
   if(vel[a]<vel[b]){
      swap(a,b);
      swap(oa,ob);
   }
   rod[b]=a;
   vel[a]+=vel[b];
   stablo[oa].push_back(ob);
   stablo[ob].push_back(oa);
   dfs(ob,oa);
}
inline int digni(int ko,int x){
   for(int i=0;i<=16;i++)
      if(x&(1<<i))
         ko=lift[ko][i];
   return ko;
}
inline int LCA(int a,int b){
   if(dub[a]>dub[b])
      swap(a,b);
   if(dub[b]>dub[a])
      b=digni(b,dub[b]-dub[a]);
   if(a==b)
      return a;
   for(int i=16;i>=0;i--)
      if(lift[a][i]!=lift[b][i]){
         a=lift[a][i];
         b=lift[b][i];
      }
   return lift[a][0];
}
void dfs2(int gde,int pret){
   for(int x:stablo[gde])
      if(x!=pret){
         dfs2(x,gde);
         kol[gde]+=kol[x];
      }
   if(pret!=0 and kol[gde]==0)
      cout<<gde<<" "<<pret<<"\n";
}
int main(){
   //cout<<sizeof(vel)+sizeof(rod)+sizeof(dub)+sizeof(lift)+sizeof(kol)<<endl;
   int a,b;
  // N=100000;
  // M=6000000;
   cin>>N>>M;
   for(int i=1;i<=N;i++){
      vel[i]=1;
      rod[i]=i;
   }
   while(M--){
      cin>>a>>b;
      if(getp(a)!=getp(b))
         spoj(a,b);
      else{
        // cout<<"DODAJEM "<<a<<" "<<b<<" "<<LCA(a,b)<<endl;
         kol[a]++;
         kol[b]++;
         kol[LCA(a,b)]-=2;
      }
   }
   //cout<<sizeof(stablo)<<endl;
   //cin>>a;
   for(int i=1;i<=N;i++)
      if(dub[i]==0)
         dfs2(i,0);
   return 0;
}
/*
10 11
1 7
1 8
1 6
2 8
6 7
5 8
2 5
2 3
2 4
3 4
10 9
*/

Subtask #1
0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6748 KB Output is correct
2 Correct 4 ms 6904 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 6748 KB Output is correct
2 Correct 169 ms 6748 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 7000 KB Output is correct
2 Runtime error 380 ms 18260 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 511 ms 7516 KB Output is correct
2 Runtime error 459 ms 21844 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 700 ms 12056 KB Output is correct
2 Runtime error 601 ms 31060 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1079 ms 13120 KB Output is correct
2 Runtime error 1144 ms 46600 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1407 ms 14112 KB Output is correct
2 Runtime error 1379 ms 55460 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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