oj.uz

Submission #1060643

# Submission time Handle Problem Language Result Execution time Memory
1060643 2024-08-15T20:13:56 Z NemanjaSo2005 Pipes (CEOI15_pipes) C++17
30 / 100
 4460 ms 56016 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;
vector<int> V;
void dfs(int gde,int pret){
   V.push_back(gde);
   lift[gde][0]=pret;
   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,bool ost=false){
   int 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];
   if(ost){
      stablo[oa].push_back(ob);
      stablo[ob].push_back(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];
}
int main(){
/*
   ifstream inf;
    ofstream ouf;
    inf.open("Input.txt");
    ouf.open("Output1.txt");
    #define cin inf*/
   // #define cout ouf

   int a,b;
   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,true);
   }
   for(int i=1;i<=N;i++)
      if(lift[i][0]==0)
         dfs(i,0);
   dub[0]=-1;
   for(int x:V)
      dub[x]=dub[lift[x][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]++;
         kol[LCA(a,b)]-=2;
      }
      else
         spoj(a,b,false);
   }
   int x;
   for(int i=V.size()-1;i>=0;i--){
      x=V[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";
  // inf.close();
   // ouf.close();
   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 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 654 ms 7004 KB Output is correct
2 Runtime error 803 ms 18300 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1060 ms 9556 KB Output is correct
2 Runtime error 957 ms 23636 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1334 ms 13704 KB Output is correct
2 Runtime error 1170 ms 31704 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2156 ms 14288 KB Output is correct
2 Runtime error 2149 ms 47340 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2883 ms 14656 KB Output is correct
2 Runtime error 2653 ms 56016 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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