Submission #568954

#	Time	Username	Problem	Language	Result	Execution time	Memory
568954		almothana05	Bridges (APIO19_bridges)	C++14	0 / 100	2150 ms	9292 KiB

bridges

#include<bits/stdc++.h>
#define mod 1000000007
#define inf 10000000000000000
using namespace std;
vector<vector<int> >edge;
vector<vector<int> >gr[100000];
int seg[500000] ,f[500000];
int sucher(int id , int l , int r , int gewl , int gewr , int gew){
   if(l > gewr || gewl > r){
      return r + 1;
   }
   int m = (l + r)/2 , cmp;
   if(gewl <= l && r <= gewr){
      if(l != r && seg[id] < gew){
         if(seg[id * 2 + 1] >= gew){
            return sucher(id * 2 , l , m , gewl , gewr , gew);
         }
         else{
            return sucher(id * 2 + 1 , m + 1 , r , gewl , gewr , gew);
         }
      }
      else if(seg[id] >= gew){
         return l;
      }
      else{
         return r + 1;
      }
   }
   cmp = sucher(id * 2 + 1 , m + 1 , r , gewl , gewr , gew);
   if(cmp != m + 1 && gewl <= m + 1 && m + 1 <= gewr){
      return cmp;
   }
   return sucher(id * 2 , l , m ,gewl , gewr , gew);
}
int finder(int id , int l , int r , int gewl , int gewr , int gew){
   // cout << l << ' ' << r << "  " << gewl << ' ' << gewr << ' ' << seg[id] <<"\n";
   // cout
   if(l > gewr || gewl > r){
      return l - 1;
   }
   int m = (l + r)/2 , cmp;
   if(gewl <= l && r <= gewr){
      if(l != r && seg[id] < gew){
         // cout << seg[id * 2] << " ja\n";
         if(seg[id * 2 ] >= gew){
            return finder(id * 2 + 1 , m + 1 , r , gewl , gewr , gew);
         }
         else{
            return finder(id * 2  , l , m , gewl , gewr , gew);
         }
      }
      else if(seg[id] >= gew){
         // cout << seg[id] << "\n";
         return r;
      }
      else{
         return l - 1;
      }
   }
   cmp = finder(id * 2  , l , m , gewl , gewr , gew);
   if(cmp != m && gewl <= m  && m  <= gewr ){
      return cmp;
   }
   return finder(id * 2 + 1, m + 1 , r ,gewl , gewr , gew);
}


int main(){
   // ios_base::sync_with_stdio(false);
   // cin.tie(NULL);
   string s;
   int menge , numm , nummer , ed , cmp , que , comp ;;
   cin >> menge >> ed;
   for(int i = 0 ; i < ed ; i++){
      cin >> numm >> nummer >> cmp;
      if(nummer > numm){
         swap(nummer , numm);
      }
      f[numm ] = cmp; 
      edge.push_back({numm , gr[numm].size() - 1 , nummer , gr[nummer].size() - 1});
   }

   int len;
   for( len = 1; len < menge ; len *= 2);
   // cout << len << "\n";
   for(int i = 0 ; i < menge ; i++){
      seg[i + len] = f[i + 1];
   }
   for(int i = 0 ; i < len ; i++){
      if(seg[i + len] == 0){
         seg[i + len] = mod;
      }
   }
   for(int i = len - 1; i > 0 ; i--){
      seg[i] = min(seg[i * 2] , seg[i * 2 + 1]);
   }
   int pl = 1;
   for(int i = 1; i < len + len ; i++){
      if(i == pl){
         // cout << "\n";
         pl *= 2;
      }
      // cout << seg[i] << " ";
   }
   cin >> que;
   while(que--){
      cin >> numm;
      if(numm == 1){
         cin >> numm >> nummer;
         numm--;
         cmp = max(edge[numm][0] , edge[numm][2]);
         seg[len + cmp - 1] = nummer;
         // cout << len + cmp - 1 << "\n";
         for(int i = (len + cmp - 1) / 2 ; i > 0 ; i--){
            seg[i] = min(seg[i * 2] , seg[i * 2 + 1]);
         }
      }
      else{
         cin >> numm >> nummer;
         // cout << len << "\n";
         cmp = sucher(1 , 1 , len , 1 , numm , nummer);
         comp = finder(1 , 1 , len , numm , menge , nummer);
         cout << comp - cmp + 1 << "\n";;
      }
   }
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:80:46: warning: narrowing conversion of '(gr[numm].std::vector<std::vector<int> >::size() - 1)' from 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   80 |       edge.push_back({numm , gr[numm].size() - 1 , nummer , gr[nummer].size() - 1});
      |                              ~~~~~~~~~~~~~~~~^~~
bridges.cpp:80:46: warning: narrowing conversion of '(gr[numm].std::vector<std::vector<int> >::size() - 1)' from 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
bridges.cpp:80:79: warning: narrowing conversion of '(gr[nummer].std::vector<std::vector<int> >::size() - 1)' from 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   80 |       edge.push_back({numm , gr[numm].size() - 1 , nummer , gr[nummer].size() - 1});
      |                                                             ~~~~~~~~~~~~~~~~~~^~~
bridges.cpp:80:79: warning: narrowing conversion of '(gr[nummer].std::vector<std::vector<int> >::size() - 1)' from 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]

• Subtask 1: 0 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27