oj.uz

Submission #698709

# Submission time Handle Problem Language Result Execution time Memory
698709 2023-02-14T08:28:32 Z Quan2003 Pipes (CEOI15_pipes) C++17
70 / 100
 1493 ms 28196 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 520 KB Output is correct
2 Correct 4 ms 572 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 5768 KB Output is correct
2 Correct 152 ms 5636 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 10244 KB Output is correct
2 Correct 290 ms 11904 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 405 ms 11608 KB Output is correct
2 Correct 312 ms 14856 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 2836 KB Output is correct
2 Runtime error 431 ms 20096 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 756 ms 3200 KB Output is correct
2 Correct 776 ms 12880 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 994 ms 4352 KB Output is correct
2 Correct 957 ms 16144 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1236 ms 4612 KB Output is correct
2 Runtime error 1245 ms 19988 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1493 ms 14496 KB Output is correct
2 Runtime error 1464 ms 28196 KB Memory limit exceeded
3 Halted 0 ms 0 KB -