Submission #698709

#	Time	Username	Problem	Language	Result	Execution time	Memory
698709		Quan2003	Pipes (CEOI15_pipes)	C++17	70 / 100	1493 ms	28196 KiB

pipes

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 1;
long long  n,q,l,r,m,bridges,lca_itr;
int vis[N + 1];
int fa_cc[N + 1];
int par[N + 1];
int fa_2ecc[N + 1];
//int comp[N + 1];
vector<pair<int,int>>ans;
int find_2ecc(int u){
    if(u == -1) return -1;
    return fa_2ecc[u] == u ? u :  fa_2ecc[u] = find_2ecc(fa_2ecc[u]);  
}
int find_cc(int u){
    u = find_2ecc(u);
    return fa_cc[u] == u ? u :  fa_cc[u] = find_cc(fa_cc[u]); 
}
void make_root(int u){
    u = find_2ecc(u); 
    int root = u; 
    int child = -1;
    while(u != -1){
        int pa = find_2ecc(par[u]);
        par[u] = child;
        fa_cc[u] = root; 
        child = u;
        u = pa; 
    }
   // comp[root] = comp[child]; 
} 
void merge(int a,int b){
     lca_itr++;
     vector<int>patha,pathb; 
     int lca = -1;
     while(lca == - 1){
         if(a != -1){
              a = find_2ecc(a);
              patha.push_back(a);
              if(vis[a] == lca_itr){
                   lca = a; 
                   break; 
              }
              vis[a] = lca_itr; 
              a = par[a]; 
         }
         if(b != -1){
             b = find_2ecc(b);
             pathb.push_back(b);
             if(vis[b] == lca_itr){
                  lca = b;
                  break; 
             }
             vis[b] = lca_itr;
             b = par[b]; 
         }
     }
     for(int i = 0; i < patha.size(); i++){
          fa_2ecc[patha[i]] = lca;
          if(patha[i] == lca) break;
          bridges--; 
     }
     for(int i = 0; i < pathb.size(); i++){
           fa_2ecc[pathb[i]] = lca; 
           if(pathb[i] == lca) break;         
           bridges--;
     }
}
int main(){
    scanf("%d%d",&n,&m); 
    for(int i = 1; i <= n; i++){
         vis[i] = 0; 
         fa_2ecc[i] = fa_cc[i] = i; 
         par[i] = -1; 
      //   comp[i] = 1;
    } 
    for(int i = 1; i <= m; i++){
         int a,b; scanf("%d%d",&a,&b); 
         int ka = a;int kb = b; 
         b = find_2ecc(a);
         a = find_2ecc(b);
         int compa = find_cc(ka);
         int compb = find_cc(kb); 
         if(compa != compb){
              ++bridges; 
              ans.push_back({ka,kb}); 
            //  if(comp[compa] > comp[compb]){
            //       swap(compa,compb);
            //       swap(a,b); 
            //  }
              make_root(a); 
              par[a] = fa_cc[a] = kb;
              //comp[compb] += comp[a];
         }
         else merge(ka,kb); 
    }
    for(int i = 0; i < ans.size(); i++){
         if(find_2ecc(ans[i].first) == find_2ecc(ans[i].second)) continue;
         cout<<ans[i].first<<' '<<ans[i].second<<endl;
    }
}

Compilation message (stderr)

pipes.cpp: In function 'void merge(int, int)':
pipes.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |      for(int i = 0; i < patha.size(); i++){
      |                     ~~^~~~~~~~~~~~~~
pipes.cpp:64:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |      for(int i = 0; i < pathb.size(); i++){
      |                     ~~^~~~~~~~~~~~~~
pipes.cpp: In function 'int main()':
pipes.cpp:71:13: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   71 |     scanf("%d%d",&n,&m);
      |            ~^    ~~
      |             |    |
      |             int* long long int*
      |            %lld
pipes.cpp:71:15: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
   71 |     scanf("%d%d",&n,&m);
      |              ~^     ~~
      |               |     |
      |               int*  long long int*
      |              %lld
pipes.cpp:98:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for(int i = 0; i < ans.size(); i++){
      |                    ~~^~~~~~~~~~~~
pipes.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
pipes.cpp:79:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |          int a,b; scanf("%d%d",&a,&b);
      |                   ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 0 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10