oj.uz

Submission #698608

# Submission time Handle Problem Language Result Execution time Memory
698608 2023-02-14T04:55:23 Z Quan2003 Pipes (CEOI15_pipes) C++17
50 / 100
 1500 ms 65536 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;
    } 
    lca_itr = 0;
    bridges = 0; 
    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:100: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]
  100 |     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:81:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |          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 0 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 340 KB Output is correct
2 Correct 151 ms 428 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 596 KB Output is correct
2 Correct 294 ms 700 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 1108 KB Output is correct
2 Correct 316 ms 15192 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 502 ms 2828 KB Output is correct
2 Runtime error 416 ms 20556 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 720 ms 3032 KB Output is correct
2 Runtime error 726 ms 35988 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 923 ms 3404 KB Output is correct
2 Runtime error 951 ms 44540 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1200 ms 3364 KB Output is correct
2 Runtime error 1190 ms 56240 KB Memory limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1487 ms 12988 KB Output is correct
2 Runtime error 1500 ms 65536 KB Memory limit exceeded
3 Halted 0 ms 0 KB -