algorithm - Hacker rank Similar Pairs -


i trying solve hacker rank similar pairs https://www.hackerrank.com/contests/101hack/challenges/similarpair problem. cant figure out why failing large test cases. using segment trees solve problem in nlogn time. can find code below.

#include<iostream> #include<vector>  using namespace std;  vector<int> graph[110001]; int t, st[100001*4] = {0}, n, deg[100001] = {0};  void update(int node, int b, int e, int idx, int val)  {      if(b > node || e < node) return;      if(b == e) {         st[idx] += val;         return;     }      update(node, b, (b + e)/2, 2 * idx, val);     update(node, (b + e)/2 + 1, e, 2 * idx + 1, val);      st[idx] = st[2 * idx]  + st[2 * idx + 1];  }  long query(int l, int r, int b, int e, int idx) {      if( l > e || r < b) return 0;      if(l <= b && r >= e) return st[idx];      return query(l, r, b, (b + e)/2, 2 * idx) + query(l, r, (b + e)/2 + 1, e, 2 * idx + 1); }  long long similarpairs(int node) {      int l = max(1, node - t), r  = min(n, node + t);     long res = 0;      res = query(l, r, 1, n, 1);      update(node, 1, n, 1, 1);      for(int = 0; < graph[node].size(); i++) {        res +=  similarpairs(graph[node][i]);     }      update(node, 1, n, 1, -1);      return res; }  int main() {      long x, y, root, result, start;       cin >> n >> t;      for(int = 0; < n - 1; i++) {         cin >> x >> y;         graph[x].push_back(y);         deg[y]++;     }      for(int = 1; <= n; i++) if(!deg[i]) root = i;      result = similarpairs(root);      cout << result << endl;      cin.get();      return 0;  }

i doing. problem missing long longs. long same int (on 32 bits), must use long long everywhere, since result not fit in 32 bit int.

this gets ac:

#include<iostream> #include<vector>  using namespace std;  vector<int> graph[110001]; int t, n, deg[100001] = {0}; long long st[100001*4] = {0};  void update(int node, int b, int e, int idx, int val)  {      if(b > node || e < node) return;      if(b == e) {         st[idx] += val;         return;     }      int m = (b + e) >> 1;     int q = idx << 1;     update(node, b, m, q, val);     update(node, m + 1, e, q + 1, val);      st[idx] = st[q]  + st[q+1];  }  long long query(int l, int r, int b, int e, int idx) {      if( l > e || r < b) return 0;      if(l <= b && r >= e) return st[idx];      int m = (b + e) >> 1;     int q = idx << 1;     return query(l, r, b, m, q) + query(l, r, m + 1, e, q + 1); }  long long similarpairs(int node) {      int l = max(1, node - t), r  = min(n, node + t);     long long res = 0;      res = query(l, r, 1, n, 1);      update(node, 1, n, 1, 1);      for(int = 0; < graph[node].size(); i++) {        res +=  similarpairs(graph[node][i]);     }      update(node, 1, n, 1, -1);      return res; }  int main() {      long x, y, root, start;       cin >> n >> t;      for(int = 0; < n - 1; i++) {         cin >> x >> y;         graph[x].push_back(y);         deg[y]++;     }      for(int = 1; <= n; i++) if(!deg[i]) root = i;      long long result = similarpairs(root);      cout << result << endl;      cin.get();      return 0;  }

Comments

Post a Comment

Popular posts from this blog

image - ClassNotFoundException when add a prebuilt apk into system.img in android -

i'm in trouble add prebuilt apk system.img based taiwan mtk android phone platform, when push apk onto device,after reboot phone,the apk can installed succecessfully,but if add apk alps/out/target/product/$prj/system/app or vendor/mediatek/$prj/artifacts/out/target/product/$prj/system/app ,and produce system.img,the apk can't installed normally,the logcat say: a.lang.runtimeexception: unable instantiate activity componentinfo{com.sec.android.widgetapp.ap.hero.accuweather.widget/com.sec.android.widgetapp.ap.hero.accuweather.widget.weatherclock}: java.lang.classnotfoundexception: com.sec.android.widgetapp.ap.hero.accuweather.widget.weatherclock. can tell me what's problem ? when package manager installs apps part of system partition different installing apps on data partition. looks app using libraries somewhere else. when install on data lib directory created in apps data directory , symlinked /data/app-lib/. when apps installed on system it's expecte...
Read more

I need to import mysql 5.1 to 5.5? -

i have mysql 5.1 database , need import localhost running 5.5. how import 5.5 or downgrade mysql? install phpmyadmin 5.1 os: http://www.wikihow.com/install-phpmyadmin-on-your-windows-pc or https://www.digitalocean.com/community/articles/how-to-install-and-secure-phpmyadmin-on-ubuntu-12-04 then login, click on database, hit export, , export in sql format (quick fine). import .sql file 5.5 server (after installing phpmyadmin) logging in clicking database , hit import. hope helps!
Read more

Java, Hibernate, MySQL - store UTC date-time -

i saw here on few related questions (like this one , of course, this one )... essentially, want store date-time utc, , let application user choose time zone wants display date-time in. since seems date-time fields affected underlying jdbc driver, wonder if acceptable way go storing utc date-time: set both mysql , application server machine utc time zone (no need separate) both mysql , jvm should pick underlying system time settings (if not instructed otherwise) use datetime table columns on mysql side use java.util.date corresponding mapping on hibernate side (i guess java.sql.timestamp used too) let application worry interpreting date-time fields - i.e. let user choose preferred time zone is ok? edit clarify - here meant refer timestamps created strictly on server (e.g.date-time of record creation). application server instantiates date objects (new date() equals current date-time on server, , time zone agnostic). if client user wants supply date searching/filte...
Read more