oj.uz

Submission #698607

# Submission time Handle Problem Language Result Execution time Memory
698607 2023-02-14T04:50:39 Z Quan2003 Pipes (CEOI15_pipes) C++17
40 / 100
 1506 ms 65536 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 4e5 + 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];
set<pair<int,int>>ans;
void init(int n){
    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; 
}
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--;
     }
}
void solve(){
    for(int i = 1; i <= m; i++){
         int a,b; scanf("%d%d",&a,&b); 
         int ka = find_2ecc(a);
         int kb = find_2ecc(b);
         int compa = find_cc(ka);
         int compb = find_cc(kb); 
         if(compa != compb){
              ++bridges; 
              ans.insert({a,b}); 
              if(comp[compa] > comp[compb]){
                   swap(compa,compb);
                   swap(ka,kb); 
              }
              make_root(ka); 
              par[ka] = fa_cc[ka] = kb;
              comp[compb] += comp[ka];
         }
         else merge(ka,kb); 
    }
    for(auto it = ans.begin(); it != ans.end(); it++){
          auto v = (*it);
          if(find_2ecc(v.first) == find_2ecc(v.second)) continue; 
          cout<<v.first<<' '<<v.second<<endl; 
    }
}
int main(){
     int t = 1;
     while(t--){
          scanf("%d%d",&n,&m); 
          init(n); 
          solve(); 
     }
}

Compilation message

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

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 5916 KB Output is correct
2 Correct 161 ms 5764 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 10548 KB Output is correct
2 Correct 303 ms 12208 KB Output is correct

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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