daily pastebin goal
20%
SHARE
TWEET

Untitled

a guest Jan 18th, 2015 173 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**********************************************
  2.             Author : smiley007  
  3. ***********************************************/
  4.  
  5. //Data Structure Includes
  6. #include <vector>
  7. #include <queue>
  8. #include <deque>
  9. #include <bitset>
  10. #include <stack>
  11. #include <list>
  12. #include <set>          
  13. #include <map>
  14.  
  15. //Other Includes
  16. #include <cstdio>
  17. #include <string>
  18. #include <cstring>
  19. #include <cstdlib>
  20. #include <iostream>
  21. #include <cmath>
  22. #include <cctype>
  23. #include <cassert>
  24. #include <numeric>
  25. #include <algorithm>
  26. #include <ctime>
  27. #include <sstream>
  28. #include <climits>
  29.  
  30. using namespace std ;
  31.  
  32. //Defines
  33. #define FOR(i,a,b)          for(int i = (a); i <  (b) ; i++)
  34. #define FOE(i,a,b)          for(int i = (a); i <= (b) ; i++)
  35. #define FOED(i,a,b)         for(int i = (a); i >= (b) ; i--)
  36. #define ITR(v,it)           for( typeof(v.begin()) it=v.begin();it!=v.end();it++)
  37. #define REP(i,n)            FOR(i,0,n)
  38. #define ALL(a)              a.begin(),a.end()
  39. #define SORT(a)             sort(ALL(a))
  40. #define SZ(a)               ((int)a.size())
  41. #define SQR(x)              ((x)*(x))
  42. #define BS(i)               __builtin_popcount(i)
  43. #define LZ(i)               __clz
  44. #define RE                  return
  45. #define FI                  first
  46. #define SD                  second
  47. #define PB                  push_back
  48. #define MP(x,y)             make_pair(x,y)
  49. #define SET(a,v)            memset(&a[0],v, sizeof(a[0])*SZ(a) )
  50. #define POW2(i)             ( 1LL << (i) )
  51. //#define SET(a,i)          a |= POW2(i)
  52. #define CLR(a,i)            a &= ~ POW2(i)
  53. #define TOGGLE(a,i)         a ^= POW2(i)
  54. #define TEST(a,i)           ((a) & POW2(i))
  55. #define EPS                 1e-9
  56. #define INF                 1e9
  57. #define PI                  3.141592653589793
  58. #define MOD                 1000000007
  59.  
  60. //Typedefs
  61. typedef long long ll ;
  62. typedef pair<int,int> pii ;
  63. typedef pair<string,string> pss ;
  64. typedef vector<int> vi ;
  65. typedef vector<ll> vl ;
  66. typedef vector<vi> vvi ;
  67. typedef vector<vl> vvl ;
  68. typedef vector<bool> vb ;
  69. typedef vector<vb> vvb ;
  70. typedef vector<string> vs ;
  71. typedef vector<pii> vpii ;
  72.  
  73. //Templates gbffgh
  74. //<< ----- Number Theory --- >>
  75. template<class T> bool isPrime(T x){if(x<=1)RE false;T i;for(i=2;i*i<=x;i++)if(x%i==0)RE false;RE true;} //isPrime
  76. template<class T> class Prime{public:vector<T> z ;Prime(){z.resize(1e5+7);REP(i,SZ(z)) z[i]=1;
  77. z[0]=0;z[1]=0;T j;FOR(i,2,SZ(z)){if(z[i]){j=i+i;while(j<SZ(z)){ z[j]=0;j += i ;} } }} }; //Prime
  78.  
  79. //<< ----- Geometry -------- >>
  80. template<class T> double dist(T x1,T y1,T x2,T y2){RE sqrt( 1.*(x2-x1)*(x2-x1) + 1.*(y2-y1)*(y2-y1) ) ;} //dist
  81. template<class T> class Point{
  82.     public :
  83.     T x, y;
  84.     Point(){}
  85.     Point(T a,T b):x(a),y(b){}
  86.     bool operator ==(const Point& tmp)const{ RE(x==tmp.x && y==tmp.y);}
  87.     Point operator-(const Point& tmp) const{ RE Point<T> (x-tmp.x,y-tmp.y);}
  88. };
  89.  
  90. //<<---- Conversions ------- >>
  91. char toLowerCase(char x){RE(x+32);}
  92. char toUpperCase(char x){RE(x-32);}
  93. bool isUpperCase(char x){RE (65<=x && x<=90)? 1 : 0 ;}
  94. bool isLowerCase(char x){RE (97<=x && x<=122)? 1 : 0 ;}
  95. bool isAlpha(char x){RE (isUpperCase(x) || isLowerCase(x))? 1 : 0 ;}
  96. bool isDigit(char x){RE('0'<=x && x<='9')? 1 : 0 ;}
  97. template<class T> T toDec(string s){stringstream is(s);T res;is>>res;RE res;} //toDec
  98. template<class T> string toStr(T n){string s;stringstream is;is<<n;is>>s;RE s;} //toStr
  99.  
  100.  
  101. template<class T> void checkmin(T& a,T b){if(a>b)a=b;}
  102. template<class T> void checkmax(T& a,T b){if(a<b)a=b;}
  103.  
  104. //Code Begins Here ------ >>>
  105. // Grab your asses fella's , because this code is gonna go deep into you :)
  106.  
  107.  
  108. int main(){
  109.     #ifdef LocalHost
  110.         freopen("input.txt","r",stdin);
  111.     #endif
  112.  
  113.     int n,m,u,v,c;
  114.     cin >> n >> m;
  115.     set<int> s;
  116.     s.clear();
  117.     vector<vector<set<int> > > g(n+1,vector<set<int> >(n+1,s));
  118.     for (int i = 0; i < m; i++) {
  119.         cin >> u >> v >> c;
  120.         g[u][v].insert(c);
  121.         g[v][u].insert(c);
  122.     }
  123.     vector<vector<set<int> > > dp = g;
  124.     for (int i = 1; i <= n; i++) {
  125.         for (int j = 1; j <= n; j++) {
  126.             if (i != j) {      
  127.                 for (int k = 1; k <= n; k++) {  
  128.                     set <int> common;
  129.                     common.clear();
  130.                     if (k == i || k == j) continue;
  131.                     ITR(dp[i][k],it) {
  132.                         if (dp[k][j].count(*it))   common.insert(*it);
  133.                     }
  134.                     ITR(common,it) {
  135.                         dp[i][j].insert(*it);
  136.                         dp[j][i].insert(*it);
  137.                     }
  138.                 }
  139.             }
  140.         }
  141.     }
  142.     int q;
  143.     cin >> q;
  144.     for (int i = 0; i < q; i++) {
  145.         cin >> u >> v;
  146.         cout << dp[u][v].size() << "\n";
  147.     }
  148.  
  149.     #ifdef LocalHost
  150.     cout<<endl<<"Execution time = "<<(float)clock()/CLOCKS_PER_SEC <<" s"<<endl;
  151.     #endif
  152.  
  153.     RE 0;
  154. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top