fork download
copy 
  1. //Coded by Vishal Mourya
  2. //If you use this code anywhere you need to mention my name as above 
  3.  
  4. #include<bits/stdc++.h>
  5. #define ll long long int 
  6. #define vec vector<ll>
  7. #define pb push_back
  8. #define f(a,b) for( ll i = a ; i < b ; i++ )
  9. #define fe(a,b) for( ll i = a ; i <= b ; i++ )
  10. #define fj(a,b) for( ll j = a ; j < b ; j++ )
  11. #define fk(a,b) for( ll k = a ; k < b ; k++ )
  12. #define fasthoja ios_base::sync_with_stdio(false); cin.tie(NULL);
  13. #define maxN 100001
  14. #define mod 1000000007
  15. #define inf 1000000007
  16. using namespace std;
  17.  
  18. vector< pair<ll,ll> > adj[maxN];
  19. vector<ll> dist(maxN,inf);
  20. ll dp[1001][1001]; //This will store shortest diatance of every other node
  21. ll storeMax[maxN]; //This array will store maximum element from each row  
  22.  
  23. void djAlgo( ll n , ll src , ll times ) { // no. of nodes , source node , what timee it is called
  24.  
  25.     //declaring min heap
  26.     priority_queue< pair<ll,ll> , vector< pair<ll,ll> >, greater< pair<ll,ll> > > pq;
  27.     ll max = 0; //will give maximum from each row 
  28.  
  29.     pq.push( {0,src} );  // { dist of source node, source node}
  30.  
  31.     dist[src] = 0;
  32.  
  33.     while( !pq.empty() ) {
  34.  
  35.         ll curr = pq.top().second;
  36.         ll curr_d = pq.top().first;
  37.         pq.pop();
  38.  
  39.         for( auto edge : adj[curr] ) {
  40.  
  41.             if( curr_d + edge.second < dist[edge.first] ) {
  42.                 dist[edge.first] = curr_d +edge.second;
  43.  
  44.                 pq.push( {dist[edge.first], edge.first} );
  45.             }
  46.         }//end of for loop
  47.  
  48.     }//end of while loop
  49.  
  50.     fe(1,n){
  51.  
  52.       dp[times][i] = dist[i]; //filling out dp array 
  53.  
  54.       if( dist[i] > max ){
  55.         max = dist[i];
  56.         storeMax[times] = max;
  57.       } 
  58.  
  59.       dist[i] = inf;
  60.     } //end of for loop
  61.  
  62. }
  63.  
  64. void printDp( ll n ) {
  65.     fe(1,n){
  66.         fj(1,n+1) cout << dp[i][j] << " ";
  67.         cout << "\n";
  68.     }
  69. }
  70.  
  71. void init1() {
  72.  
  73.     //This function will initialize everything used globally like array,adj list,etc 
  74.     f(0,maxN) {
  75.  
  76.         adj[i].clear(); //clearing previous inputs
  77.         dist[i] = inf;
  78.         storeMax[i] = 0;
  79.     }//end of for loop
  80.  
  81.     f(0,1001){
  82.         fj(0,1001) dp[i][j] = 0;
  83.     }
  84. }
  85.  
  86. ll countSetBits( ll num ) {
  87.  
  88.     return __builtin_popcount(num);  //   __builtin_popcount(4) return number of set bits in number
  89. }
  90.  
  91. void finalDp( ll n ) {
  92.  
  93.     fe(1,n){
  94.         fj(1,n+1) {
  95.  
  96.             ll setBit1 = countSetBits( dp[i][j] );
  97.             ll setBit2 = countSetBits( storeMax[i] );
  98.  
  99.             dp[i][j] = ( setBit1 ^ setBit2 );
  100.  
  101.         }//end of inner for loop
  102.  
  103.  
  104.     }//end of outer for loop
  105. }
  106.  
  107. void init2( ll n ) {
  108.  
  109.     //This function will fill our dp array voila !!
  110.     fe(1,n){
  111.         //Start wil 1 
  112.         djAlgo( n , i , i );
  113.     }//end of for loop 
  114.  
  115.     finalDp(n); //for doing xor operations 
  116.  
  117. } //end of init2 function 
  118.  
  119. int main(void){
  120.  
  121.     fasthoja;
  122.     ll t; cin>>t;
  123.     while(t--){
  124.  
  125.         init1();
  126.         ll n,m; cin >> n >> m;
  127.         while(m--) {
  128.  
  129.             ll a,b,w;
  130.             cin >> a >> b;
  131.             //as mentioned distance is abs( b*b - a*a )
  132.             w = abs( (b*b) - (a*a) );
  133.             adj[a].pb( {b,w} );
  134.             adj[b].pb( {a,w} );
  135.         }
  136.  
  137.         init2(n);
  138.  
  139.  
  140.         ll q; cin >> q;
  141.         while(q--) { // query loop
  142.  
  143.             ll l,r; cin >> l >> r; //query range
  144.             cout << dp[l][r] << "\n";
  145.  
  146.         }//end of query loop
  147.  
  148.         cout << "\n";
  149.  
  150.     } //end of test case loop 
  151.     return 0;
  152. }//end of main function
Success #stdin #stdout 0s 14888KB
comments (?)
stdin
copy 
1
6 9
1 2
1 6
2 6
2 3
3 6
3 5
3 4 
4 5 
5 6 
4
1 2
2 5
6 4
3 3
stdout
copy 
1
2
1
4
https://ideone.com/ZS5zvu
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!