Solution of Light OJ 1109 - False Ordering

/* Bismillahir Rahmanir Rahim Saving number of divisor for every number and sorting using structure. */ #include<bits/stdc++.h> using namespace std; int t, n, i, j, cs=1; struct all{ int num; int ds; }one[1001]; bool comp(all f, all s){ // sort of structure if(f.ds==s.ds) return f.num>s.num; else return f.ds<s.ds; } void cal(){ // main calculation for all numbers for(i=1; i<=1000; i++){ one[i].num=i; one[i].ds=1; } for(i=1; i<=500; i++){ for(j=2*i; j<=1000; j+=i){ one[j].ds=one[j].ds+1; } } } int main(){ cal(); sort(one, one+1001, comp); cin>>t; while(t--){ cin>>n; cout<<"Case "<<cs++<<": "<<one[n].num<<endl; } return 0; }

Solution of Light OJ 1099 - Not the Best

/* Bismillahir Rahmanir Rahim Solution-Using Dijkstra. Calculate shortest path and second shortest path for each node */ #include<bits/stdc++.h> #define fi(n, m) for(int i=n; i<=m; i++) #define ll long long using namespace std; vector<ll>vt[5009], cost[5009]; ll n, en, d1[5009], d2[5009], sz; //d2[]=second shortest, d1[]=shortest struct node{ ll u, w; node(ll a, ll b){ u=a, w=b; } bool operator < (const node & p)const{ return p.w<w; } }; void dijkstra(int st){ priority_queue<node>q; q.push(node(st, 0)); fi(1, n){d1[i]=30000000, d2[i]=30000000;} d1[st]=0; while(!q.empty()){ node top=q.top(); q.pop(); int u=top.u; sz=vt[u].size(); fi(0, sz-1){ int v=vt[u][i]; int uu=cost[u][i]; // mind it if(d1[u]+uu<d1[v]){ ll temp=d1[v]; d1[v]=d1[u]+uu; d2[v]=min(temp, min(d2[v], min(d2[u]+uu, d1[u]+3*uu))); q.push(node(v, d1[v]+d2[v])); } else if(d1[u]+uu<d2[v] && (d1[u]+uu)>d1[v]){ d2[v]=d1[u]+uu; } else{ d2[v]=min(d2[v], min(d2[u]+uu, d1[u]+3*uu)); } } } } int main(){ int t, cs=1, st, e, u, v, w, nn, ans; cin>>t; while(t--){ cin>>n>>e; fi(1, e){ cin>>u>>v>>w; vt[u].push_back(v); vt[v].push_back(u); cost[u].push_back(w); cost[v].push_back(w); } ll back=100000009; // Its for a special case, given bellow fi(0, vt[1].size()-1){ back=min(back, 2*cost[1][i]); } dijkstra(1); back=d1[n]+back; cout<<"Case "<<cs++<<": "<<min(back, d2[n])<<endl; fi(0, n){ vt[i].clear(); cost[i].clear(); } } return 0; } /* Special Case Input: 1 4 5 1 2 3 2 3 7 3 4 4 1 2 4 4 1 4 Output: Case 1: 10 */

Solution of Light OJ 1257 - Farthest Nodes in a Tree (II)

We may solve using BFS of DFS. Both solutions are given.
Using BFS:

/* Bismillahir Rahmanir Rahim Solution-Using BFS Find the farthest two nodes and calculate all nodes distance from both farthest nodes and take the maximum for each node */ #include<bits/stdc++.h> #define fi(n, m) for(int i=n; i<=m; i++) #define fii(i, n, m) for(int i=n; i<=m; i++) using namespace std; vector<int>vt[30001], cost[30001]; int n, dis[30001], dis1[30001], a1, a2, p, cnt=0; void bfs(int st){ fi(0, n) dis[i]=-1; int mx=-1; queue<int>q; q.push(st); dis[st]=0; while(!q.empty()){ int u=q.front(); q.pop(); if(mx<dis[u]){ mx=dis[u]; p=u; } for(int j=0; j<vt[u].size(); j++){ int v=vt[u][j]; if(dis[v]==-1){ dis[v]=dis[u]+cost[u][j]; q.push(v); } } } } void bfs1(int st){ fi(0, n) dis1[i]=-1; queue<int>q; q.push(st); dis1[st]=0; while(!q.empty()){ int u=q.front(); q.pop(); for(int j=0; j<vt[u].size(); j++){ int v=vt[u][j]; if(dis1[v]==-1){ dis1[v]=dis1[u]+cost[u][j]; q.push(v); } } } } int main() { int t, cs=1, u, v, w; scanf("%d", &t); while(t--){ scanf("%d", &n); fi(1, n-1){ scanf("%d%d%d", &u, &v, &w); vt[u].push_back(v); vt[v].push_back(u); cost[u].push_back(w); cost[v].push_back(w); } bfs(0); // find an ending point of farthest path a1=p; // find another ending point a2 and distance from a1 (dis[]) bfs(a1); a2=p; bfs1(a2); //calculating distance from a2(dis1[]) printf("Case %d:\n", cs++); fi(0, n-1){ printf("%d\n", max(dis[i], dis1[i])); vt[i].clear(); cost[i].clear(); } } return 0; }

Using DFS:

/* Bismillahir Rahmanir Rahim Solution-Using DFS Find the farthest two nodes and calculate all nodes distance from both farthest nodes and take the maximum for each node */ #include<bits/stdc++.h> #define fi(n, m) for(int i=n; i<=m; i++) #define fii(i, n, m) for(int i=n; i<=m; i++) using namespace std; vector<int>vt[30009], cost[30009]; int dis[30009], dis1[30009], vis[30009], n, p, mx; void dfs(int at){ if(vis[at]) return ; else{ vis[at]=1; if(mx<dis[at]){ mx=dis[at]; p=at; } for(int j=0; j<vt[at].size(); j++){ int v=vt[at][j]; if(dis[v]==-1){ dis[v]=dis[at]+cost[at][j]; dfs(v); } } } } void dfs1(int at){ if(vis[at]) return ; else{ vis[at]=1; for(int j=0; j<vt[at].size(); j++){ int v=vt[at][j]; if(dis1[v]==-1){ dis1[v]=dis1[at]+cost[at][j]; dfs1(v); } } } } int main(){ int t, cs=1, u, v, w, a1, a2; scanf("%d", &t); while(t--){ scanf("%d", &n); fi(1, n-1){ scanf("%d%d%d", &u, &v, &w); vt[u].push_back(v); vt[v].push_back(u); cost[u].push_back(w); cost[v].push_back(w); } fi(0, n+1){vis[i]=0; dis[i]=-1;} mx=0, dis[0]=0; dfs(0); // find an ending point of farthest path a1=p, mx=0; fi(0, n+1){vis[i]=0; dis[i]=-1;} dis[a1]=0; // find another ending point a2 and distance from a1(dis[]) dfs(a1); a2=p; fi(0, n+1){vis[i]=0; dis1[i]=-1;} dis1[a2]=0; dfs1(a2);//calculating distance from a2(dis1[]) printf("Case %d:\n", cs++); fi(0, n-1){ printf("%d\n", max(dis[i], dis1[i])); vt[i].clear(); cost[i].clear(); } } return 0; }