oj.uz

Submission #1060666

# Submission time Handle Problem Language Result Execution time Memory
1060666 2024-08-15T20:31:46 Z NemanjaSo2005 Pipes (CEOI15_pipes) C++17
100 / 100
 4963 ms 14420 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];
vector<pair<int,int>> R;
int S[maxn],cnt=0,c2=0,S2[100];
int getp(int x){
   while(rod[x]!=x){
      S2[++c2]=x;
      x=rod[x];
   }
   while(c2>0){
      rod[S2[c2]]=x;
      c2--;
   }
   return x;
}
int main(){
   int a,b,oa,ob;
   int x;
   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)){
         oa=a;
         ob=b;
         a=getp(a);
         b=getp(b);
         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);
      }
   }
   for(int i=1;i<=N;i++)
      if(lift[i][0]==0){
         S[++cnt]=i;
         for(int j=cnt;j<=cnt;j++){
            for(int x:stablo[S[j]]){
               if(x==lift[S[j]][0])
                  continue;
               lift[x][0]=S[j];
               S[++cnt]=x;
            }
         }
      }

   dub[0]=-1;
   for(int i=1;i<=N;i++)
      dub[S[i]]=dub[lift[S[i]][0]]+1;
   for(int j=1;j<=16;j++)
      for(int i=1;i<=N;i++)
         lift[i][j]=lift[lift[i][j-1]][j-1];

   cin.clear(); // Clear the EOF flag
   cin.seekg(0, std::ios::beg);

   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)){
         kol[a]++;
         kol[b]++;

         if(dub[a]>dub[b])
            swap(a,b);
         if(dub[b]>dub[a]){
            x=dub[b]-dub[a];
            for(int i=0;i<=16;i++)
               if(x&(1<<i))
                  b=lift[b][i];
         }
         if(a!=b){
            for(int i=16;i>=0;i--)
               if(lift[a][i]!=lift[b][i]){
                  a=lift[a][i];
                  b=lift[b][i];
               }
            a=lift[a][0];
         }
         kol[a]-=2;
      }
      else{
         a=getp(a);
         b=getp(b);
         if(vel[a]<vel[b]){
            rod[a]=b;
            vel[b]+=vel[a];
         }
         else{
            rod[b]=a;
            vel[a]+=vel[b];
         }
      }
   }
   for(int i=N;i>=1;i--){
      x=S[i];
      for(int y:stablo[x])
         if(y!=lift[x][0])
            kol[x]+=kol[y];
      if(kol[x]==0 and lift[x][0]!=0)
         R.push_back({min(x,lift[x][0]),max(x,lift[x][0])});
   }
   sort(R.begin(),R.end());
   for(auto x:R)
      cout<<x.first<<" "<<x.second<<"\n";
   return 0;
}
/*
10 13
2 6
7 2
5 10
10 3
3 4
5 8
9 7
4 2
7 9
5 8
1 3
3 7
2 1
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 402 ms 6492 KB Output is correct
2 Correct 379 ms 6704 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1144 ms 9556 KB Output is correct
2 Correct 972 ms 9628 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1524 ms 13140 KB Output is correct
2 Correct 1304 ms 13136 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2357 ms 13652 KB Output is correct
2 Correct 2462 ms 13640 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3083 ms 14308 KB Output is correct
2 Correct 3001 ms 14320 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4116 ms 14244 KB Output is correct
2 Correct 3812 ms 14420 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4963 ms 14132 KB Output is correct
2 Correct 4701 ms 14416 KB Output is correct