It's a basic implementation of centroid decomposed tree. Though after reading a while and solving a couple of problems i'm still unable to understand the necessity(and intuition) behind the centroid decomposition.The only time i think its useful is when two nodes are on two different subtree and then lca(on CD tree) can store some information about them.
For this specific problem.
In CD-tree, if two nodes have same rank,then they must have a common ancestor.
Ac in one go!Thanks to Hussain's hints.
#include <bits/stdc++.h>using namespace std ;#define DEBUG(x) cout << '>' << #x << ':' << x << endl;#define mem(x,val) memset((x),(val),sizeof(x))#define all(x) x.begin(),x.end()#define pb push_back#define mp make_pair#define PI acos(-1.0)#define MAXN 111111const int INF = 1 << 29 ;typedef long long ll ;typedef pair < int , int > pii ;priority_queue <pair < pair < double , int > , pii > > pq ;vector <pair < int , pii > > g[MAXN] ;int sumA , sumB ;bool visited[MAXN] ;
straightforward implementation of Floyd Warshall algorithm.just treat k as a[k] where a[k] is the array of ranked cities.
#include <bits/stdc++.h>using namespace std ;#define DEBUG(x) cout << '>' << #x << ':' << x << endl;#define mem(x,val) memset((x),(val),sizeof(x))#define all(x) x.begin(),x.end()#define pb push_back#define mp make_pair#define PI acos(-1.0)#define MAXN 11111const int INF = 1 << 29 ;typedef long long ll ;typedef pair < int , int > pii ;int dp[152][152][151] , a[151];int main() {
find out the digit dp.for 1:
here is the solution.
#include <bits/stdc++.h>using namespace std ;#define DEBUG(x) cout << '>' << #x << ':' << x << endl;#define mem(x,val) memset((x),(val),sizeof(x))#define all(x) x.begin(),x.end()#define pb push_back#define mp make_pair#define PI acos(-1.0)#define MAXN 11111#define MOD 1000000007#define rep(i ,start , n) for(int i = start ;i<= n ; i++)
my recurrence relation goes like :
and watch out for the negatives.
#include <bits/stdc++.h>using namespace std ;#define DEBUG(x) cout << '>' << #x << ':' << x << endl;#define mem(x,val) memset((x),(val),sizeof(x))
learned how to transform linear recurrence into matrix form and awesome matrix exponentiation implementation from fushar blog .
#include <bits/stdc++.h>using namespace std ;#define DEBUG(x) cout << '>' << #x << ':' << x << endl;#define mem(x,val) memset((x),(val),sizeof(x))#define all(x) x.begin(),x.end()#define pb push_back#define mp make_pair#define PI acos(-1.0)#define MOD 1000000007#define REP(i ,n) for(int i = 1 ;i<=n ;i++)const int INF = 1 << 29 ;typedef long long ll ;typedef pair < int , int > pii ;typedef vector < vector < ll > > matrix ;
what a great problem!never thought of implementing dijkstra like this:
small intuition:Suppose x is the smallest number of set A and s_num[r] is the smallest number correspond to remainder r. now if input gives a number y such that y<s_num[r] and y%x == r.how can we prove that y can't be made from set A?
==> suppose we can make y from set A.then as per the smallest value concern we must choose y to be in the smallest number for remainder 'r' . as it didn't happen.our initial assumption is not true.so we can't make y from set A.
#include <bits/stdc++.h>using namespace std ;#define DEBUG(x) cout << '>' << #x << ':' << x << endl;#define mem(x,val) memset((x),(val),sizeof(x))#define all(x) x.begin(),x.end()
This problem caused me a lot of troubles.thanks to Hussain's insights.specifically 2:
1.you need to deploy a dummy node.as bellman ford is SSSP algorithm.
2.you need to reverse the direction of the edges.cause upon reversing if you can relax any edge u→v in nth iteration .3things can happen:
1.Either both u and v is part of negative cycle.
2.one of them is a part of negative cycle.
3.none of them is part of negative cycle
in all of the three cases you can always visit the negative cycle from u and v(inclusive) .
Using set .with no optimization.implementation credit : Michal Forišek's answer to What is the most simple & efficient C++ code for Dijkstra's shortest path algorithm?
#include <bits/stdc++.h>using namespace std ;#define DEBUG(x) cout << '>' << #x << ':' << x << endl;#define mem(x,val) memset((x),(val),sizeof(x))#define all(x) x.begin(),x.end()#define pb push_back#define mp make_pair#define PI acos(-1.0)#define MAXN 11111const int INF = 1 << 29 ;typedef long long ll ;typedef pair < int , int > pii ;int dijkstra(vector < vector <pii > > &g , int start , int target) {vector < int > d(g.size()+1 , INT_MAX) ;d[start] = 0 ;set < pii > city ;
#include <bits/stdc++.h>using namespace std ;#define DEBUG(x) cout << '>' << #x << ':' << x << endl;#define mem(x,val) memset((x),(val),sizeof(x))#define all(x) x.begin(),x.end()#define pb push_back#define mp make_pair#define PI acos(-1.0)#define MAXN 111111const int INF = 1 << 29 ;typedef long long ll ;typedef pair < int , int > pii ;vector < int > g[MAXN] ;int cnt = 0 ;bool visited[MAXN] ;void dfs(int u) {cnt++ ;visited[u] = true ;for(int i = 0 ;i<g[u].size() ;i++)
