API tools faq
paste
Advertisement
Mohammad_Dipu_Sultan

Cobbled streets SPOJ - CSTREET || MST

Mohammad_Dipu_Sultan
Sep 30th, 2021
988
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 11.76 KB | None | 0 0
raw download clone embed print report
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long           ll;
  5. typedef unsigned long long  ull;
  6. typedef double              ld;//%Lf
  7. #define ff                  first
  8. #define ss                  second
  9. #define pb                  push_back
  10. #define mp                  make_pair
  11. #define ppb                 pop_back
  12. #define in                  insert
  13. #define sz(a)               int((a).size())
  14. #define vi                  vector<int>
  15. #define vl                  vector<ll>
  16. #define vvi                 vector<vector<int> >
  17. #define pii                 pair<int,int>
  18. #define piii                pair<int,pair<int,int> >
  19. #define pll                 pair<ll,ll>
  20. #define vii                 vector<pii>
  21. #define vll                 vector<pll>
  22. #define viii                vector<piii>
  23. #define YES                 cout << "YES\n"
  24. #define NO                  cout << "NO\n"
  25.  
  26. #define scl(n)              scanf("%lld",&n)
  27. #define scll(x,y)           scanf("%lld %lld",&x,&y)
  28. #define gtl(x)              getline(cin, (x))
  29.  
  30. #define f0(b)               for(int i=0;i<(b);i++)
  31. #define f00(b)              for(int j=0;j<(b);j++)
  32. #define f1(b)               for(int i=1;i<=(b);i++)
  33. #define f11(b)              for(int j=1;j<=(b);j++)
  34. #define f2(a,b)             for(int i=(a);i<=(b);i++)
  35. #define f22(a,b)            for(int j=(a);j<=(b);j++)
  36. #define RFOR(i,x,y)         for(int i=x;i>=y;i--)
  37. #define all(v)              v.begin(),v.end()
  38. #define rall(v)             v.rbegin(),v.rend()
  39. #define unq(v)              sort(all(v)),(v).resize(unique(all(v))-v.begin())
  40. #define present(c,x)        ((c).find(x) != (c).end())
  41. #define cpresent(c,x)       (find(all(c),x) != (c).end())
  42. #define min_ele(v)          (*min_element(all(v)))
  43. #define max_ele(v)          (*max_element(all(v)))
  44. #define cnt_ele(v, x)       (count(all(v), x))
  45. #define sum_ele(v)          (accumulate(all(v),0))
  46. #define reversed(s)         reverse(s.begin(), s.end())
  47.  
  48. #define testcase            ll t; cin>>t; while (t--)
  49. #define vout(v)             for(int ind=0;ind<v.size();ind++){ cout<<v[ind]; if(ind<v.size()-1) cout<<' '; else cout<<endl;}
  50. #define arrout(arr,i,x,y)   for(int i=x;i<=y;i++){ cout<<arr[i]; if(i<y) cout<<' '; else cout<<endl;}
  51. #define PI                  acos(-1)
  52. #define CLR(x, y)           memset(x, y, sizeof(x))
  53. #define Precision(a)        cout << fixed << setprecision(a)
  54. #define BITCH_FAST()        ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0) //Don't use scanf/printf
  55. #define MAXP                1000006
  56. #define MOD                 1e9+7//10000007 // For big mod
  57. #define EPS                 1e-7
  58.  
  59. template <typename T> T Sqr(T x) { T n = x * x ; return n ;}
  60. template <typename T> T Pow(T B,T P){ if(P==0) return 1; if(P&1) return B*Pow(B,P-1);  else return Sqr(Pow(B,P/2));}
  61. template <typename T> T Abs(T a) {if(a<0)return -a;else return a;}
  62. template <typename T> T Gcd(T a,T b){if(a<0)return Gcd(-a,b);if(b<0)return Gcd(a,-b);return (b==0)?a:Gcd(b,a%b);} // better than __gcd
  63. template <typename T> T Lcm(T a,T b) {if(a<0)return Lcm(-a,b);if(b<0)return Lcm(a,-b);return a*(b/Gcd(a,b));}
  64. template <typename T> T power(T n, T p){ T res = 1;while(p > 0){if(p & 1)res *= n;n *= n;p >>= 1;}return res;}
  65. template <typename T> T BigMod (T b,T p,T m){if (p == 0) return 1;if (p%2 == 0){T s = BigMod(b,p/2,m);return ((s%m)*(s%m))%m;}return ((b%m)*(BigMod(b,p-1,m)%m))%m;}
  66. template <typename T> inline string ToBinary(T n) {string r ;while(n != 0) {r = ( n % 2 == 0 ? "0" : "1" ) + r ; n >>= 1;} return r ;}
  67. long long BinaryToDecimal(string s) {int len = s.size();long long n = 0, p = 1;for (int i = len - 1; i >= 0; i-- , p *= 2) n += p * (s[i] - '0');return n;}
  68. int Strtoint(string str){stringstream ss(str);int x = 0;ss >> x ;return x ;}
  69. string Intostr(int x){stringstream ss; ss << x; string str = ss.str(); return str;}
  70.  
  71. /*----------------------Graph Moves----------------*/
  72. int ROW[]={+1,-1,+0,+0};
  73. int COL[]={+0,+0,+1,-1};
  74.  
  75. int X[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
  76. int Y[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
  77.  
  78. int KX[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
  79. int KY[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
  80. vi parent, raank;
  81. viii edges;
  82. void makeset(int n)
  83. {
  84.     for(int i=0; i<n; i++)
  85.     {
  86.         parent[i]=i;
  87.         raank[i]=0;
  88.     }
  89. }
  90. int find_parent(int v)
  91. {
  92.     if(parent[v]==v)
  93.     {
  94.         return v;
  95.     }
  96.     return parent[v]=find_parent(parent[v]);
  97. }
  98. void union_seet(int u, int v)//Join
  99. {
  100.     u=find_parent(u);
  101.     v=find_parent(v);
  102.     if(u!=v)
  103.     {
  104.         if(rand()%2)
  105.         {
  106.             swap(u, v);
  107.         }
  108.         parent[v]=u;
  109.     }
  110. }
  111.  
  112. int Kruskals(viii &edges)
  113. {
  114.     int wt=0;
  115.     sort(all(edges));
  116.     for(auto e:edges)
  117.     {
  118.         int u=e.ss.ff;
  119.         int v=e.ss.ss;
  120.         int set_u=find_parent(u);
  121.         int set_v=find_parent(v);
  122.         if(set_u!=set_v)
  123.         {
  124.             wt+=e.ff;
  125.             union_seet(u,v);
  126.         }
  127.     }
  128.     return wt;
  129.  
  130. }
  131. int main()
  132. {
  133.     BITCH_FAST();
  134.     #ifdef FLAME
  135.         clock_t tStart = clock();
  136.         freopen("input.txt", "r", stdin);
  137.         freopen("output.txt", "w", stdout);
  138.     #endif
  139.     testcase
  140.     {
  141.         int p, n, m;
  142.         cin >> p >> n >> m;
  143.         viii edges;
  144.         edges.clear();
  145.         parent.resize(n+5);
  146.         raank.resize(n+5);
  147.         makeset(n+2);
  148.         f0(m)
  149.         {
  150.             int a, b, c;
  151.             cin >> a >> b >> c;
  152.             edges.push_back({c,{a, b}});
  153.         }
  154.         ll krs=Kruskals(edges);
  155.         cout << krs*p << endl;
  156.     }
  157.     #ifdef FLAME
  158.         fprintf(stderr, "\n>> Runtime: %.10fs\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);
  159.     #endif
  160.     return 0;
  161. }
  162.  
  163. //Type 2
  164. #include<bits/stdc++.h>
  165. using namespace std;
  166.  
  167. typedef long long           ll;
  168. typedef unsigned long long  ull;
  169. typedef double              ld;//%Lf
  170. #define ff                  first
  171. #define ss                  second
  172. #define pb                  push_back
  173. #define mp                  make_pair
  174. #define ppb                 pop_back
  175. #define in                  insert
  176. #define sz(a)               int((a).size())
  177. #define vi                  vector<int>
  178. #define vl                  vector<ll>
  179. #define vvi                 vector<vector<int> >
  180. #define pii                 pair<int,int>
  181. #define piii                pair<int,pair<int,int> >
  182. #define pll                 pair<ll,ll>
  183. #define vii                 vector<pii>
  184. #define vll                 vector<pll>
  185. #define viii                vector<piii>
  186. #define YES                 cout << "YES\n"
  187. #define NO                  cout << "NO\n"
  188.  
  189. #define scl(n)              scanf("%lld",&n)
  190. #define scll(x,y)           scanf("%lld %lld",&x,&y)
  191. #define gtl(x)              getline(cin, (x))
  192.  
  193. #define f0(b)               for(int i=0;i<(b);i++)
  194. #define f00(b)              for(int j=0;j<(b);j++)
  195. #define f1(b)               for(int i=1;i<=(b);i++)
  196. #define f11(b)              for(int j=1;j<=(b);j++)
  197. #define f2(a,b)             for(int i=(a);i<=(b);i++)
  198. #define f22(a,b)            for(int j=(a);j<=(b);j++)
  199. #define RFOR(i,x,y)         for(int i=x;i>=y;i--)
  200. #define all(v)              v.begin(),v.end()
  201. #define rall(v)             v.rbegin(),v.rend()
  202. #define unq(v)              sort(all(v)),(v).resize(unique(all(v))-v.begin())
  203. #define present(c,x)        ((c).find(x) != (c).end())
  204. #define cpresent(c,x)       (find(all(c),x) != (c).end())
  205. #define min_ele(v)          (*min_element(all(v)))
  206. #define max_ele(v)          (*max_element(all(v)))
  207. #define cnt_ele(v, x)       (count(all(v), x))
  208. #define sum_ele(v)          (accumulate(all(v),0))
  209. #define reversed(s)         reverse(s.begin(), s.end())
  210.  
  211. #define testcase            ll t; cin>>t; while (t--)
  212. #define vout(v)             for(int ind=0;ind<v.size();ind++){ cout<<v[ind]; if(ind<v.size()-1) cout<<' '; else cout<<endl;}
  213. #define arrout(arr,i,x,y)   for(int i=x;i<=y;i++){ cout<<arr[i]; if(i<y) cout<<' '; else cout<<endl;}
  214. #define PI                  acos(-1)
  215. #define CLR(x, y)           memset(x, y, sizeof(x))
  216. #define Precision(a)        cout << fixed << setprecision(a)
  217. #define BITCH_FAST()        ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0) //Don't use scanf/printf
  218. #define MAXP                1000006
  219. #define MOD                 1e9+7//10000007 // For big mod
  220. #define EPS                 1e-7
  221.  
  222. template <typename T> T Sqr(T x) { T n = x * x ; return n ;}
  223. template <typename T> T Pow(T B,T P){ if(P==0) return 1; if(P&1) return B*Pow(B,P-1);  else return Sqr(Pow(B,P/2));}
  224. template <typename T> T Abs(T a) {if(a<0)return -a;else return a;}
  225. template <typename T> T Gcd(T a,T b){if(a<0)return Gcd(-a,b);if(b<0)return Gcd(a,-b);return (b==0)?a:Gcd(b,a%b);} // better than __gcd
  226. template <typename T> T Lcm(T a,T b) {if(a<0)return Lcm(-a,b);if(b<0)return Lcm(a,-b);return a*(b/Gcd(a,b));}
  227. template <typename T> T power(T n, T p){ T res = 1;while(p > 0){if(p & 1)res *= n;n *= n;p >>= 1;}return res;}
  228. template <typename T> T BigMod (T b,T p,T m){if (p == 0) return 1;if (p%2 == 0){T s = BigMod(b,p/2,m);return ((s%m)*(s%m))%m;}return ((b%m)*(BigMod(b,p-1,m)%m))%m;}
  229. template <typename T> inline string ToBinary(T n) {string r ;while(n != 0) {r = ( n % 2 == 0 ? "0" : "1" ) + r ; n >>= 1;} return r ;}
  230. long long BinaryToDecimal(string s) {int len = s.size();long long n = 0, p = 1;for (int i = len - 1; i >= 0; i-- , p *= 2) n += p * (s[i] - '0');return n;}
  231. int Strtoint(string str){stringstream ss(str);int x = 0;ss >> x ;return x ;}
  232. string Intostr(int x){stringstream ss; ss << x; string str = ss.str(); return str;}
  233.  
  234. #define TRACE
  235. #ifdef TRACE
  236. #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
  237.     template <typename Arg1>
  238.     void __f(const char* name, Arg1&& arg1){
  239.         cout << name << " : " << arg1 << endl;
  240.         //use cerr if u want to display at the bottom
  241.     }
  242.     template <typename Arg1, typename... Args>
  243.     void __f(const char* names, Arg1&& arg1, Args&&... args){
  244.         const char* comma = strchr(names + 1, ','); cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
  245.     }
  246. #else
  247. #define trace(...)
  248. #endif
  249.  
  250. /*----------------------Graph Moves----------------*/
  251. int ROW[]={+1,-1,+0,+0};
  252. int COL[]={+0,+0,+1,-1};
  253.  
  254. int X[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
  255. int Y[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
  256.  
  257. int KX[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
  258. int KY[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
  259. int find_parent(vii &roots,int v)
  260. {
  261.     if(roots[v].ss==v)
  262.     {
  263.         return v;
  264.     }
  265.     return roots[v].ss=find_parent(roots,roots[v].ss);
  266. }
  267. void union_seet(vii &roots, int u, int v)//Join
  268. {
  269.     u=find_parent(roots, u);
  270.     v=find_parent(roots, v);
  271.     if(roots[u].ff>roots[v].ff)
  272.     {
  273.         roots[v].ss=u;
  274.     }
  275.     else
  276.     {
  277.         roots[u].ss=v;
  278.     }
  279.     if(roots[u].ff==roots[v].ff)
  280.     {
  281.         roots[v].ff++;
  282.     }
  283. }
  284.  
  285. int Kruskals(viii &edges, int n)
  286. {
  287.     int wt=0;
  288.     sort(all(edges));
  289.     vii roots(n+5);
  290.     f0(n+2)
  291.     {
  292.         roots[i]={0,i};
  293.     }
  294.     for(auto e:edges)
  295.     {
  296.         int u=e.ss.ff;
  297.         int v=e.ss.ss;
  298.         int set_u=find_parent(roots, u);
  299.         int set_v=find_parent(roots, v);
  300.         if(set_u!=set_v)
  301.         {
  302.             union_seet(roots, u, v);
  303.             wt+=e.ff;
  304.         }
  305.     }
  306.     return wt;
  307. }
  308. int main()
  309. {
  310.     BITCH_FAST();
  311.     #ifdef FLAME
  312.         clock_t tStart = clock();
  313.         freopen("input.txt", "r", stdin);
  314.         freopen("output.txt", "w", stdout);
  315.     #endif
  316.     testcase
  317.     {
  318.         int p, n, m;
  319.         cin >> p >> n >> m;
  320.         viii edges;
  321.         int sum=0;
  322.         f0(m)
  323.         {
  324.             int a, b, c;
  325.             cin >> a >> b >> c;
  326.             edges.push_back({c,{a, b}});
  327.         }
  328.         ll krs=Kruskals(edges, m);
  329.         cout << krs*p << endl;
  330.     }
  331.     #ifdef FLAME
  332.         fprintf(stderr, "\n>> Runtime: %.10fs\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);
  333.     #endif
  334.     return 0;
  335. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!