We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
#include<stdlib.h>#include<stdio.h>#include<math.h>#include<string.h>#include<assert.h>#include<limits.h>#include<time.h>#define swapI_(x, y) { int z = x; x = y; y = z; }#define swapIp_(x, y) { int *z = x; x = y; y = z; }#define nMax 25000#define xMax 10000000typedeflonglongll;typedefstructV{intparent;intgc;intgs[7];}V;typedefstructL{intval;intnext;}L;intn;Vvs[nMax+1];intdepths[nMax+1];intgc=1;intprimeC=446;intprimes[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1013,1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,1087,1091,1093,1097,1103,1109,1117,1123,1129,1151,1153,1163,1171,1181,1187,1193,1201,1213,1217,1223,1229,1231,1237,1249,1259,1277,1279,1283,1289,1291,1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,1381,1399,1409,1423,1427,1429,1433,1439,1447,1451,1453,1459,1471,1481,1483,1487,1489,1493,1499,1511,1523,1531,1543,1549,1553,1559,1567,1571,1579,1583,1597,1601,1607,1609,1613,1619,1621,1627,1637,1657,1663,1667,1669,1693,1697,1699,1709,1721,1723,1733,1741,1747,1753,1759,1777,1783,1787,1789,1801,1811,1823,1831,1847,1861,1867,1871,1873,1877,1879,1889,1901,1907,1913,1931,1933,1949,1951,1973,1979,1987,1993,1997,1999,2003,2011,2017,2027,2029,2039,2053,2063,2069,2081,2083,2087,2089,2099,2111,2113,2129,2131,2137,2141,2143,2153,2161,2179,2203,2207,2213,2221,2237,2239,2243,2251,2267,2269,2273,2281,2287,2293,2297,2309,2311,2333,2339,2341,2347,2351,2357,2371,2377,2381,2383,2389,2393,2399,2411,2417,2423,2437,2441,2447,2459,2467,2473,2477,2503,2521,2531,2539,2543,2549,2551,2557,2579,2591,2593,2609,2617,2621,2633,2647,2657,2659,2663,2671,2677,2683,2687,2689,2693,2699,2707,2711,2713,2719,2729,2731,2741,2749,2753,2767,2777,2789,2791,2797,2801,2803,2819,2833,2837,2843,2851,2857,2861,2879,2887,2897,2903,2909,2917,2927,2939,2953,2957,2963,2969,2971,2999,3001,3011,3019,3023,3037,3041,3049,3061,3067,3079,3083,3089,3109,3119,3121,3137};intgetG(intp){staticintgs[xMax+1];if(!gs[p]){gs[p]=gc++;}returngs[p];}voidwriteFactors(){for(inti=1;i<=n;++i){intx;scanf("%d",&x);inty=(int)sqrt(x);int*gs=vs[i].gs;intps[3];ints=0;for(intt=0;t<primeC;++t){intp=primes[t];if(p>y){break;}if(x%p==0){ps[s]=p;gs[s++]=getG(p);x/=p;while(x%p==0)x/=p;y=(int)sqrt(x);}}if(x>1){ps[s]=x;gs[s++]=getG(x);}if(s==2){gs[s++]=getG(ps[0]*ps[1]);}elseif(s==3){gs[s++]=getG(ps[0]*ps[1]);gs[s++]=getG(ps[0]*ps[2]);gs[s++]=getG(ps[1]*ps[2]);gs[s++]=getG(ps[0]*ps[1]*ps[2]);}vs[i].gc=s;}}voidwriteParents(){staticintnexts[nMax+1];staticcharhits[nMax+1];staticLls[(nMax-1)*2+1];staticintdata[nMax*2];int*is=data;int*js=&data[nMax];intic=0;intjc=0;intt=1;for(ints=0;s<n-1;++s){inti,j;scanf("%d %d",&i,&j);ls[t].val=j;ls[t].next=nexts[i];nexts[i]=t;t++;ls[t].val=i;ls[t].next=nexts[j];nexts[j]=t;t++;}ic=1;is[0]=1;hits[1]=1;intdepth=0;while(ic>0){for(ints=0;s<ic;++s){inti=is[s];depths[i]=depth;intt=nexts[i];while(t){intj=ls[t].val;t=ls[t].next;if(!hits[j]){vs[j].parent=i;js[jc++]=j;hits[j]=1;}}}swapIp_(is,js);ic=jc;jc=0;depth++;}}#define run(i) \ {\ sum += vc;\ int *gs = vs[i].gs;\ switch (vs[i].gc)\ {\ case 1:\ sum -= cs[gs[0]]++;\ break;\ case 3:\ sum -= cs[gs[0]]++;\ sum -= cs[gs[1]]++;\ sum += cs[gs[2]]++;\ break;\ case 7:\ sum -= cs[gs[0]]++;\ sum -= cs[gs[1]]++;\ sum -= cs[gs[2]]++;\ sum += cs[gs[3]]++;\ sum += cs[gs[4]]++;\ sum += cs[gs[5]]++;\ sum -= cs[gs[6]]++;\ break;\ }\ vc++;\ i = vs[i].parent;\ }voidsolveQuery(){inti,j;staticintcs[xMax+1];scanf("%d %d",&i,&j);intvc=0;llsum=0;if(depths[i]<depths[j]){swapI_(i,j);}intm=depths[i]-depths[j];for(ints=0;s<m;++s){run(i);}while(i!=j){run(i);run(j);}run(i);printf("%lld\n",sum);for(ints=0;s<gc;++s){cs[s]=0;}}voidprint(){for(inti=1;i<=n;++i){printf("%d: parent=%d, depth=%d, %d, %d, %d\n",i,vs[i].parent,depths[i],vs[i].gs[0],vs[i].gs[1],vs[i].gs[2]);}}intmain(){intqc;scanf("%d %d",&n,&qc);writeFactors();writeParents();//print();for(intq=0;q<qc;++q){solveQuery();}return0;}
I don't understand the answer to the first query for the sample input; the value (number of coprime edges in the path from node 4 to node 6) is shown as 9, but I don't see how it can be any value greater than 5. Here's my thinking:
1. It says the graph is undirected, connected, with nEdges = nNodes - 1.
2. This means the graph is a tree (acyclic) so there is a unique path between nodes.
3. The maximum length of a shortest path between two nodes can't exceed the number of edges, which is 5.
What's going on?
what is wrong with this code...gives timeout error after test case 9...I did BFS before processing the query and then taking LCA of each query..finally finds
Here is my solution in java, javascript, Python, C, C++,Csharp HackerRank Coprime Paths Problem Solution
https://zeroplusfour.com/coprime-paths-hackerrank-solution/ Here's how I did in all languages Java 8 , C++ , C , Python 3, Python 2.
C solution
I don't understand the answer to the first query for the sample input; the value (number of coprime edges in the path from node 4 to node 6) is shown as 9, but I don't see how it can be any value greater than 5. Here's my thinking: 1. It says the graph is undirected, connected, with nEdges = nNodes - 1. 2. This means the graph is a tree (acyclic) so there is a unique path between nodes. 3. The maximum length of a shortest path between two nodes can't exceed the number of edges, which is 5. What's going on?
what is wrong with this code...gives timeout error after test case 9...I did BFS before processing the query and then taking LCA of each query..finally finds
the path.