NOI Reference
Last edited: 15th
March 2018
Graph Theory
Depth First Search O(V+E)
vector<pi> adjlist[N];
bool visited[N];
int dist[N];
void dfs(int x){
if(visited[x]) return;
visited[x] = true;
for(auto i : adjlist[x]){
if(visited[i]) continue;
dist[i] = dist[x]+i.second; // dist only valid for
trees!
dfs(i);
}
}
Toposort (DFS) O(V+E)
vector<int> adjList[N],
topo;
bool visited[N];
void dfs (int x) {
if (visited[x]) return;
visited[x] = 1;
for (auto i : adjList[x]) {
if (visited[i]) continue;
dfs(i);
}
topo.push_back(x); // post ordering
}
/* Usage */
topo.clear();
memset(visited, 0,
sizeof(visited));
for (int i = 0; i < N;
++i) {
if (visited[i]) continue;
dfs(i);
}
reverse(topo.begin(),
topo.end()); //to get the correct topological order
Breadth First Search O(V+E)
int dx[8] = {-1, 0, 1, -1, 1,
-1, 0, 1};
int dy[8] = {-1, -1, -1, 0,
0, 1, 1, 1};
int dist[H][W];
dist[sx][sy] = 0;
q.push(pi(sx, sy)); // x,y
while(!q.empty()){
int x = q.front().first.first;
int y = q.front().first.second;
q.pop();
for(int i = 0; i<8; i++){
int newx = x+dx[i]; int newy = y+dy[i];
if(!valid(newx, newy)) continue;
if(!visited[newx][newy]){
dist[newx][newy] = dist[x][y]+1; // only for
unweighted graphs
q.push(pi(newx, newy));
}
}
}
UFDS Amortized O(1)
int p[N];
int findSet(int x){
if(p[x] == x) return x;
else return p[x] = findSet(p[x]);
}
bool same(int x, int y){
return findSet(x) == findSet(y);
}
void merge(int x, int y){
p[findSet(x)] = findSet(y);
}
Floyd (APSP) O(V3)
int adjmat[N][N];
// remember adjmat[i][i] == 0
for(int k = 0; k<N; k++){
// intermediate node outside
for(int i = 0; i<N; i++){
for(int j = 0; j<N; j++){
if(adjmat[i][k] == -1 or adjmat[k][j] == -1)
continue;
if(adjmat[i][j] == -1 or
adjmat[i][j]>adjmat[i][k]+adjmat[k][j])
adjmat[i][j] =
adjmat[i][j]+adjmat[k][j];
}
}
}
Bellman-Ford (SSSP) O(NE)
dist[s]=0; //dist all others
= INF
for (int i=0; i<N-1; i++){
for (int j=0; j<E; j++){
dist[v]=min(dist[v],dist[u]+c); // dir edge from u to
v with c cost
}
}
Dijkstra(SSSP) O(ElogN)
priority_queue<pi,
vector<pi>, greater<pi>> pq; // greater is important!
memset(dist, -1, sizeof
dist);
dist[source] = 0;
pq.push(pi(0, source));
while(!pq.empty()){
int node = pq.top().second; int d =
pq.top().first; pq.pop();
if(dist[node] != d) continue; // important!
for(auto i : adjlist[node]){
int childnode = i.first, childdist =
i.second;
if(dist[childnode] == -1 or dist[childnode] > dist[node] +
childdist){
//note: strictly greater than is important!
dist[childnode] = dist[node] + childdist;
pq.push(pi(dist[childnode], childnode));
}
}
}
Dijkstra Variant (Longest
Path, Positive Cycle Detection) (problem: girlfriend)
#include
<bits/stdc++.h>
#define INF -2
using namespace std;
typedef pair<int, int>
pi;
vector<pi>
adjlist[100050];
bool infinite[100050];
int visited[100050];
priority_queue<pi> pq;
int dist[100050];
int n,e,source,dest;
void dfs(int x){
if(visited[x]) return;
visited[x] = 1;
for(auto i : adjlist[x]){
if(visited[i.first] == 0) dfs(i.first);
else if(visited[i.first] == 1) infinite[i.first] =
true;
}
visited[x] = 2;
}
int main(){
cin >> n >> e >> source >> dest;
for(int i = 0; i<e; i++){
int a,b,c;
cin >> a >> b >> c;
adjlist[a].push_back(pi(b,c));
}
memset(dist, -1, sizeof dist);
for(int i = 0; i<n; i++) if(visited[i] == 0) dfs(i);
if(infinite[source])
dist[source] = -2; else dist[source] = 0;
pq.push(pi(dist[source], source));
while(!pq.empty()){
int node = pq.top().second; int d = pq.top().first;
pq.pop();
if(d != dist[node]) continue;
for(auto i : adjlist[node]){
int childnode = i.first; int childdist =
i.second;
if(dist[node] == INF){
if(dist[childnode] == INF) continue;
dist[childnode] = INF;
pq.push(pi(dist[childnode], childnode));
}else if(dist[childnode] == INF) continue;
else if(dist[childnode] == -1 or
(dist[childnode] < dist[node] + childdist)){
if(infinite[childnode]) dist[childnode]
= INF;
else dist[childnode] = dist[node] +
childdist;
pq.push(pi(dist[childnode], childnode));
}
}
}
}
Dijkstra with Ways Counting
memset(dist, -1, sizeof
dist);
dist[source] = 0;
ways[source] = 1;
pq.push(pi(0,source));
while(!pq.empty()){
int node = pq.top().second; int d =
pq.top().first; pq.pop();
if(dist[node] != d) continue;
for(auto i : adjlist[node]){
int childnode = i.first;
int childdist = i.second;
if(dist[childnode] == -1 or dist[childnode]
> dist[node] + childdist){
dist[childnode] = dist[node]+childdist;
ways[childnode] = ways[node];
pq.push(pi(dist[childnode], childnode));
}else if(dist[childnode] ==
dist[node]+childdist) {
ways[childnode] += ways[node];
}
}
}
Dijkstra with Shortest Path
DAG
memset(from, -1, sizeof
from);
memset(dist, -1, sizeof
dist);
dist[source] = 0;
from[source] = -1;
pq.push(pi(0,source));
while(!pq.empty()){
ll node = pq.top().second; ll d = pq.top().first; pq.pop();
if(dist[node] != d) continue;
for(auto i : adjlist[node]){
ll childnode = i.first;
ll childdist = i.second;
if(dist[childnode] == -1 or dist[childnode] >
dist[node] + childdist){
dist[childnode] = dist[node]+childdist;
from[childnode] = node;
pq.push(pi(dist[childnode], childnode));
}
}
}
0-1 BFS (SSSP on 0-1 edges)
O(E+V)
memset(dist, -1, sizeof
dist);
dist[source] = 0;
pq.push_front(pi(0, source));
while(!pq.empty()){
int node = pq.front().second; int d =
pq.front().first;
if(dist[node] != d) continue;
for(auto i : adjlist[node]){
int childnode = i.first, childdist =
i.second; // childdist == 0 or 1
if(dist[childnode] == -1 or dist[childnode]
> dist[node] + childdist){
dist[childnode] = dist[node] + childdist;
if(childdist == 1){
pq.push_back(pi(dist[childnode],
childnode));
}else{
pq.push_front(pi(dist[childnode],
childnode));
}
}
}
}
SPFA(SSSP) (untested)
typedef pair<int,int>
pi;
vector<pi>
adjList[10000]; // node, weight
queue<int> q; // node
bitset<10000> in_q; //1
if node is in queue, bitset is same as bool array
int dist[10000];
memset(dist, -1,
sizeof(dist)); // initialise to -1, representing infinity
q.push(source); dist[source]
= 0; in_q[source] = 1;
while(!q.empty()){
int c = q.front();
q.pop();
in_q[c] = 0;
for(auto i : adjList[c]){
if(dist[i.first] == -1 || dist[i.first] > dist[c] +
i.second){
dist[i.first] = dist[c] + i.second;
if (!in_q[i.first]) q.push(i.first);
in_q[i.first] = 1;
}
}
}
Bipartite Matching
bool dfs(int x){
if(visited[x]) return false;
visited[x] = true;
for(auto i : adjlist[x]){
if(color[i] == color[x]){ /*clash*/ }
color[i] = 3-color[x];
if(!visited[i]) {
if(dfs(i)) { /*clash*/ }
}
}
return false; // no clash
}
Kruskal (MST) O(ElogV)
//UFDS
int p[N];
int findSet(int x){
if(p[x] == x) return x;
else return p[x] = findSet(p[x]);
}
bool same(int x, int y){
return findSet(x) == findSet(y);
}
void merge(int x, int y){
p[findSet(x)] = findSet(y);
}
sort(edgelist+1,
edgelist+e+1);
int totalcost = 0;
for(int i = 1; i <= e;
i++){
int cost = edgelist[i].first;
int firstguy = edgelist[i].second.first;
int secondguy = edgelist[i].second.second;
if (same(firstguy, secondguy)) continue;
totalcost += cost;
merge(firstguy, secondguy);
}
Prim (MST) O(ElogV)
typedef pair<int,int>
pi;
vector<pi>
adjList[10000]; // node, weight
priority_queue<pi,
vector<pi>, greater<pi> > pq;
bool visited[10000];
pq.push(pi(0, 0));
while(!pq.empty()){
pi c = pq.top();
pq.pop();
if(visited[c.second]) continue;
visited[c.second] = true;
for(auto i : adjList[c.second]){
if(!visited[i.second]){
pq.push(pi(i.second, i.first));
}
}
}
Tree Diameter
int treediam(){
memset(visited, false, sizeof visited);
memset(dist, -1, sizeof dist);
dist[V[0]] = 0;
dfs(V[0]);
int furthestdist = -1, furthestindex = 0;
for(int i = 0; i<n; i++){
if(dist[i] > furthestdist){
furthestdist = dist[i];
furthestindex = i;
}
}
memset(visited, false, sizeof visited);
memset(dist, -1, sizeof dist);
dist[furthestindex] = 0;
furthestdist = -1;
for(int i = 0; i<n; i++){
if(dist[i] > furthestdist){
furthestdist = dist[i];
furthestindex = i;
}
}
return furthestdist;
}
TSP on Tree
int ans = 0;
int V[N]; // nodes to visit
bool goals[N]; // whether
node is a place to visit
// find the subtree
bool dfs(ll x){
if(visited[x]) return false;
visited[x] = true;
bool need=false;
if(goals[x]) need=true;
for(auto i : adjlist[x]){
if(dfs(i.first)) ans+=i.second, need=true;
}
return need;
}
dfs(V[0]);
ans*=2; // subtree weights *
2
ans -= treediam(); // minus the tree diameter
2k Decomposition
<O(NlogN), O(logN)>
int p[100050][20];
vector<int>
adjlist[100050];
int q,n;
void roottree(int x, int
par){
p[x][0] = par;
for(auto i : adjlist[x]){
if(i.first == par) continue;
dist[i.first] = dist[x] + i.second;
depth[i.first] = depth[x]+1;
roottree(i.first, x);
}
}
void tkd(){
for(int k = 1; k<20; k++){
for(int i = 0; i<n; i++){
if(p[i][k-1] != -1){
p[i][k] = p[p[i][k-1]][k-1];
}else p[i][k] = -1;
}
}
}
int query(int x, int k){
for(int i = 20; i>=0; i--){
if(k>=(1<<i)){
if(x!=-1) x = p[x][i];
k-=(1<<i);
}
}
return x;
}
LCA
// 2KD
int lca(int a, int b){
if(depth[a] < depth[b]) swap(a,b);
for(int k = 19; k>=0; k--){
if(p[a][k] != -1 and depth[p[a][k]] >=
depth[b]){
a = p[a][k];
}
}
if(a==b) return a;
for(int k = 19; k>=0; k--){
if(p[a][k] != p[b][k]) a=p[a][k],
b=p[b][k];
}
return p[a][0];
}
APSP
//LCA
int apsp(int a, int b){
return dist[a]+dist[b]-2*dist[lca(a,b)];
}
MCBM (Augmenting Path) (slow)
vector<int>
adjlist[255];
int p[255];
bool visited[255];
int aug(int x){
if(visited[x]) return 0;
visited[x] = true;
for(auto i : adjlist[x]){
if(p[i] == -1 or aug(p[i])){
p[i] = x;
p[x] = i;
return 1;
}
}
return 0;
}
memset(p, -1, sizeof p);
int ans = 0;
for(auto i : left){
memset(visited, false, sizeof visited); //
very important***
if(p[i] == -1) ans += aug(i);
}
Note: On Bipartite Graph,
|MVC| == |MCBM| (Knigճ Theorem)
Note: On Bipartite Graph,
|MIS| == |V|-|MCBM|
MCBM (Hopcroft Karp) (fast)
O(sqrt(V)E)
#define MAX 100001 // edit
accordingly
#define nil 0
#define inf INT_MAX
using namespace std;
struct MCBM{
vector<int> adjlist[MAX];
int n, m, match[MAX], dist[MAX];
// n: number of nodes on left side, nodes are numbered 1 to n
// m: number of nodes on right side, nodes are numbered n+1 to
n+m
// G = nil[0] _ G1[G[1---n]] _ G2[G[n+1---n+m]] // important!!
MCBM(int nn, int mm){
n = nn;
m = mm;
}
bool bfs() {
int i, u, v, len;
queue< int > Q;
for(i=1; i<=n; i++) {
if(match[i]==nil) {
dist[i] =
0;
Q.push(i);
}
else dist[i]
= inf;
}
dist[nil] = inf;
while(!Q.empty()) {
u = Q.front();
Q.pop();
if(u!=nil) {
for(auto
v : adjlist[u]){
if(dist[match[v]]==inf) {
dist[match[v]] = dist[u] + 1;
Q.push(match[v]);
}
}
}
}
return (dist[nil]!=inf);
}
bool dfs(int u) {
int i, v, len;
if(u!=nil) {
len =
adjlist[u].size();
for(i=0;
i<len; i++) {
v =
adjlist[u][i];
if(dist[match[v]]==dist[u]+1) {
if(dfs(match[v])) {
match[v] = u;
match[u] = v;
return true;
}
}
}
dist[u] =
inf;
return false;
}
return true;
}
int hopcroft_karp() {
int matching = 0, i;
// match[] is assumed nil for all vertex in adjlist
while(bfs())
for(i=1;
i<=n; i++)
if(match[i]==nil && dfs(i))
matching++;
return matching;
}
void addEdge(int u, int v){ // left to right
assert(v>n);
adjlist[u].push_back(v);
}
}; //usage MCBM g(n,m);
g.addEdge(a,b);
Tarjanճ SCC
#include
<bits/stdc++.h>
using namespace std;
typedef pair<int, int>
pi;
int n,e;
vector<int>
adjlist[100050]; // normal adjlist
int disc[100050],
low[100050]; // required for tarjan
bool onstack[100050];
//required for tarjan
int inSCC[100050]; // which
scc a node is in
set<int>
sccAdjlist[100050]; // scc adjlist
vector<int> s, newscc;
vector<vector<int>
> SCCs; // list of sccs
vector<pi> edgelist; //
normal edgelist
int counter = 0;
void scc(int x){
disc[x] = low[x] = counter++;
s.push_back(x);
onstack[x] = true;
for(auto i : adjlist[x]){
if(disc[i] == -1){
scc(i);
low[x] = min(low[x], low[i]);
}
else if(onstack[i]){
low[x] = min(low[x], disc[i]);
}
}
if(disc[x] == low[x]){
newscc.clear();
do{
newscc.push_back(s.back());
onstack[s.back()] = false;
inSCC[s.back()] = SCCs.size();
s.pop_back();
}while(newscc[newscc.size()-1] != x);
SCCs.push_back(newscc);
}
}
int main(){
memset(disc, -1, sizeof disc);
cin >> n >> e;
for(int i = 0; i<e; i++){
int a,b;
cin >> a >> b;
adjlist[a].push_back(b);
edgelist.push_back(pi(a,b));
}
for(int i = 0; i<n; i++) if(disc[i] == -1) scc(i);
for(auto i : edgelist){
sccAdjlist[inSCC[i.second]].insert(inSCC[i.first]);
}
for(int i = 0; i<SCCs.size(); i++){
if(sccAdjlist[i].find(i) != sccAdjlist[i].end())
sccAdjlist[i].erase(sccAdjlist[i].find(i));
}
}
Transitive Closure O(V^2)
bool trans[2050][2050];
void dfs(int x, int y){
trans[x][y] = true;
for(auto i : adjlist[y]){
if(!trans[x][i]) dfs(x,i);
}
}
int main(){
for(int i = 0; i<n; i++){
dfs(i,i);
}
}
Random ҴeleportӠsolution
int visited[500050];
int pre[500050];
int ctr = 0;
int stopat = -1;
int n, A[500050];
int dfs(int x){
if(visited[x] > 0) return visited[x];
if(visited[x] == -1){
visited[x] = ctr-pre[x];
stopat = x;
return -visited[x];
}
pre[x] = ctr++;
visited[x] = -1;
int ret = dfs(A[x]);
if(ret < 0){
visited[x] = -ret;
if(stopat == x){
stopat = -1;
return -ret;
}
return ret;
}
visited[x] = ret + 1;
return visited[x];
}
Articulation points
(bombing2)
#include
<bits/stdc++.h>
using namespace std;
typedef pair<int, int>
pi;
bool visited[200050];
int depth[200050];
int low[200050];
int parent[200050];
set<int>
adjlist[200050];
int childcount = 0;
int components[200050];
int n,e;
vector<int>
articulationpoints;
int d = 0;
int atp(int x){
visited[x] = true;
depth[x] = d;
low[x] = d;
d++;
childcount = 0;
for(auto i : adjlist[x]){
if(!visited[i]){
parent[i] = x;
atp(i);
if(low[i] >= depth[x]){
components[x]++;
}
low[x] = min(low[x], low[i]);
}else if(i != parent[x]) low[x] = min(low[x],
depth[i]);
}
}
int main(){
parent[0] = -1;
cin >> n >> e;
for(int i = 0; i<e; i++){
int a,b; cin >> a >> b;
adjlist[a].insert(b);
adjlist[b].insert(a);
}
atp(0);
int ans = components[0];
for(int i = 1; i<n; i++){
ans = max(ans, components[i]+1);
// printf("%d: %d\n", i, components[i]);
}
cout << ans;
}
Pseudocode:
GetArticulationPoints(i, d)
visited[i] = true
depth[i] = d
low[i] = d
childCount = 0
isArticulation = false
for each ni in adj[i]
if not visited[ni]
parent[ni] = i
GetArticulationPoints(ni, d + 1)
childCount = childCount + 1
if low[ni] >= depth[i]
isArticulation = true
low[i] = Min(low[i], low[ni])
else if ni <> parent[i]
low[i] = Min(low[i], depth[ni])
if (parent[i] <> null and isArticulation) or
(parent[i] == null and childCount > 1)
Output i as articulation point
Articulation Bridges
Pseudocode:
GetBridges(i, d)
visited[i] = true
depth[i] = d
low[i] = d
for each ni in adj[i]
if not visited[ni]
parent[ni] = i
GetBridges(ni, d + 1)
if low[ni] > depth[i]
Output i,ni as bridge
low[i] = Min(low[i], low[ni])
else if ni <> parent[i]
low[i] = Min(low[i], depth[ni])
Centroid Decomposition
int nn = 0; // num nodes
int subsize[100050];
int cpar[100050];
void dfs1(int x, int p){ //
compute subtree sizes
subsize[x] = 1;
nn++;
for(auto i : adjlist[x]){
if(i == p) continue;
dfs1(i, x);
subsize[x] += subsize[i];
}
}
int dfs2(int x, int p){ //
finds the centroid in subtree rooted at x
for(auto i : adjlist[x]){
if(i == p) continue;
if(subsize[i] > nn/2) return dfs2(i, x);
}
return x;
}
void decomp(int x, int p){
nn = 0;
dfs1(x, x);
int centroid = dfs2(x,x);
if(p == -1) p=centroid;
cpar[centroid] = p;
for(auto i : adjlist[centroid]){
adjlist[i].erase(centroid);
decomp(i, centroid);
}
adjlist[centroid].clear();
}
// called with decomp(0, -1);
Centroid Decomp (primedst)
#include
<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dist[20][50050]; // depth
of tree, dist to centroid
ll subsize[50005];
ll nn = 0;
ll n;
vector<ll> primes;
set<ll> adjlist[50050];
bitset<50050> isPrime;
void calcsize(ll x, ll p){
subsize[x] = 1;
nn++;
for(auto i : adjlist[x]){
if(i == p) continue;
calcsize(i, x);
subsize[x] += subsize[i];
}
}
ll centroid(ll x, ll p){
for(auto i : adjlist[x]){
if(i == p) continue;
if(subsize[i] > nn/2) return centroid(i, x);
}
return x;
}
void edit(ll x, ll p, ll
depth, ll d, ll change){
// update the subtree at depth, x, all by change
dist[depth][d] += change;
for(auto i : adjlist[x]){
if(i == p) continue;
edit(i, x, depth, d+1, change); // recurse on children
}
}
ll getadd(ll x, ll p, ll
depth, ll d){ // this node is currently at distance d away
ll ret = 0;
for(auto i : primes){
if(i-d < 0) continue;
ll add = dist[depth][i-d]; // number of nodes, i-d away
from centroid
if(add == 0) break;
if(i == d) add*=2;
ret += add;
}
for(auto i : adjlist[x]){
if(i != p) ret+=getadd(i,x,depth,d+1);
}
return ret;
}
ll ans = 0;
void decomp(ll x, ll depth){
nn = 0;
calcsize(x, x);
ll cen = centroid(x,x);
edit(cen, cen, depth, 0, 1); // make all one
ll add=0;
for(auto i : adjlist[cen]){
edit(i,cen,depth,1,-1); // remove this subtree
contribution
add+=getadd(i,cen,depth,1); // get the contributions
edit(i,cen,depth,1,1); // change back
}
ans += add;
for(auto i : adjlist[cen]){
adjlist[i].erase(cen);
decomp(i, depth+1);
}
for(ll i = 0; i<=n; i++) dist[depth][i] = 0;
}
void genprimes(){
isPrime.reset(); isPrime.flip();
isPrime[2] = true;
primes.push_back(2);
for(ll i = 2; i*2 <= n+10; i++) isPrime[i*2] = false;
for(ll i = 3; i<=n+10; i+=2){
if(!isPrime[i]) continue;
primes.push_back(i);
for(ll j = 2; i*j<=n+10; j++) isPrime[i*j] = false;
}
}
int main(){
freopen("input.txt", "r", stdin);
cin >> n;
genprimes();
for(ll i = 0; i<n; i++){
ll a,b;
cin >> a >> b;
adjlist[a].insert(b);
adjlist[b].insert(a);
}
decomp(1,1);
double a = (double) ans / 2.0; // divide by two because double
counting
double b = ((double) n * (double) (n-1)) / 2.0;
cout << a/b;
}
LCA to RMQ & Euler Tour
Decomp (ants) Version #1
#include
<bits/stdc++.h>
#include "ants.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll>
pi;
vector<pi>
adjlist[100050];
ll fw[200050];
ll S[100050], E[100050];
ll ctr=1;
ll n, edges;
// lca setup
int st[200050][19]; //
s[x][0] is self
int pre[100050];
int pre_r[100050];
int prectr = 1;
void dfs(int x, int p){
pre[x] = prectr;
pre_r[prectr] = x;
prectr++;
for(auto i : adjlist[x]){
if(i.first == p) continue;
dfs(i.first, x);
}
}
void update(ll p, ll v){
for(;p<=2*edges+9;p+=p&(-p)) fw[p] += v;
}
ll query(ll x, ll y){
ll ans = 0;
for(;y;y-=y&(-y)) ans+=fw[y];
x--;
for(;x;x-=x&(-x)) ans-=fw[x];
return ans;
}
void printfw(){
for(int i=1; i<=2*edges+9; i++) printf("%d ",
query(i, i)); printf("\n");
}
void roottree(ll x, ll p, ll
d){
st[ctr][0] = pre[x];
S[x] = ctr++;
for(auto i : adjlist[x]){
if(i.first == p) continue;
update(ctr, i.second);
roottree(i.first, x, d+i.second);
update(ctr, -i.second);
st[ctr][0] = pre[x];
ctr++;
}
E[x] = ctr;
}
void sparse_init(){
for(int k = 1; k<=16; k++){
for(int i = 0; i<2*edges+9; i++){
st[i][k] = min( st[i][k-1],
st[i+(1<<(k-1))][k-1] );
}
}
}
int minq(int x, int y){ //
[x, y]
// if(x>y) swap(x,y);
assert(x<=y);
int len = y-x+1;
int k = 32-1-__builtin_clz(len);
return min(st[x][k], st[y-(1<<k)+1][k]);
}
int lca(int x, int y){
if(S[x]
> S[y]) swap(x,y);
int ans = pre_r[minq(S[x], S[y])];
return ans;
}
typedef pair<pi, ll>
iii;
vector<iii> edgelist;
void tree(int _N, int _E, int
A[], int B[], int D[]) {
n = _N, edges = _E;
for(ll i = 0; i<_E; i++){
adjlist[A[i]].push_back({B[i], D[i]});
adjlist[B[i]].push_back({A[i], D[i]});
edgelist.emplace_back(iii(pi(A[i], B[i]), D[i]));
}
dfs(0, -1);
roottree(0, -1, 0);
sparse_init();
// for(ll i = 0; i<n; i++) printf("%d-%d\n", S[i],
E[i]); printf("\n");
// for(ll i = 1; i<2*edges+9; i++) printf("%d: %d\n",
i, query(i, i)); printf("\n");
// for(ll i = 1; i<2*edges+9; i++) printf("%d: %d\n",
i, st[i][0]); printf("\n");
return;
}
void adjust(int e, int v){
ll a = edgelist[e].first.first, b = edgelist[e].first.second;
ll d = edgelist[e].second;
if(S[a] > S[b]) swap(a,b);
// a is the earlier one
update(S[b], -d);
update(E[b], d);
update(S[b],
v);
update(E[b],
-v);
edgelist[e].second = v;
return;
}
ll inf = INT_MAX;
void safe(int e) { // bug
occurs when 2 0 and 2 1, and 0 1 3 (perhaps use lca stuff)
ll a = edgelist[e].first.first, b = edgelist[e].first.second;
if(S[a] > S[b]) swap(a,b);
// a is the earlier one
update(S[b], -inf);
update(E[b], inf);
return;
}
void dangerous(int e) {
ll a = edgelist[e].first.first, b = edgelist[e].first.second;
if(S[a] > S[b]) swap(a,b);
// a is the earlier one
update(S[b], inf);
update(E[b], -inf);
return;
}
int energy(int x, int y) {
// printf("q(%d,%d)=\n", x, y);
// printf("S(%d) to S(%d)=\n", E[x], S[y]);
int p = lca(x, y);
ll ans = query(E[x], S[p]);
ll ans2 = query(E[p], S[y]);
// ll ans2 = 0;
if(ans < -inf/2 or ans > inf/2) return 0;
if(ans2 < -inf/2 or ans2 > inf/2) return 0;
return ans+ans2;
}
PushRelabel (maxflow, mincut)
(noiref, tested) O(N^3)
typedef long long ll;
struct Edge {
int to;
ll cap, flow;
Edge(int tar, ll capacity): to(tar),
cap(capacity), flow(0) {}
ll amt() { return cap-flow; }
};
struct PushRelabel {
int N;
vector<Edge> E;
vector<vector<int> >G;
vector<int> height, cnt;
vector<bool> inq;
vector<ll> excess;
queue<int> q;
PushRelabel(int _N): N(_N), height(_N),
cnt(2*_N), inq(_N), excess(_N), G(_N) {}
void AddEdge(int a, int b, ll c) { //directed edge a -> b with capacity c
if (a == b) return;
G[a].push_back(E.size());
E.push_back({b, c});
G[b].push_back(E.size());
E.push_back({a, 0});
}
void Enqueue(int x) {
if (inq[x] || excess[x] == 0) return;
inq[x] = 1;
q.push(x);
}
void Push(int x, int ed) {
int it = E[ed].to;
if (height[x] <= height[it]) return;
ll flow = min(excess[x], E[ed].amt());
if (flow == 0) return;
E[ed].flow += flow;
E[ed^1].flow -= flow;
excess[x] -= flow;
excess[it] += flow;
Enqueue(it);
}
void Relabel(int x) {
if (excess[x] == 0) return;
--cnt[height[x]];
height[x] = 2*N;
for (auto it:G[x]) {
if (E[it].amt() == 0) continue;
height[x] = min(height[x],
height[E[it].to]+1);
}
++cnt[height[x]];
Enqueue(x);
}
void GapHeuristic(int g) {
for (int i = 0; i < N; ++i) {
if (height[i] >= g) {
--cnt[height[i]];
height[i] = max(height[i], N+1);
++cnt[height[i]];
Enqueue(i);
}
}
}
void Discharge(int x) {
for (auto it:G[x]) {
Push(x, it);
if (excess[x] == 0) return;
}
if (cnt[height[x]] == 1)
GapHeuristic(height[x]);
else Relabel(x);
}
ll MaxFlow(int S, int T) {
height[S] = N;
cnt[0] = N-1, cnt[N] = 1;
inq[S] = inq[T] = 1;
for (auto it:G[S]) {
excess[S] += E[it].cap;
Push(S, it);
}
while (!q.empty()) {
int x = q.front();
q.pop(), inq[x] = 0;
Discharge(x);
}
return excess[T];
}
vector<int> MinCut(int S, int T) {
MaxFlow(S, T);
int split = N;
vector<int> ans;
for (int i = 1; i <= N; ++i) {
if (cnt[i] == 0) {
split = i;
break;
}
}
for (int i = 0; i < N; ++i) {
if (height[i] > split)
ans.push_back(i);
}
return ans;
}
};
LCA to RMQ Version #2
(taqtree)
#include
<bits/stdc++.h>
using namespace std;
typedef pair<int, int>
pi;
int n,q;
vector<pi>
adjlist[100050];
int pre[100050],
pre_r[100050]; // pre maps node to pre-ordering, pre_r maps pre-ordering to
node
int fw[200050];
int S[100050], E[100050];
int st[500050][19];
void add(int p, int v){
for(;p<=2*n+10;p+=p&(-p)) fw[p] += v;
}
int query(int a, int b){
int ans = 0;
int p = a-1;
assert(p != -1);
for(;p;p-=p&(-p)) ans-=fw[p];
p = b;
for(;p;p-=p&(-p)) ans+=fw[p];
return ans;
}
struct edge{
int a,b,c;
edge();
edge(int aa, int bb, int cc){ a = aa, b = bb, c = cc; }
};
vector<edge> edgelist;
int prectr = 1;
void preorder(int x, int
par){ // this is for lca (rmq)
pre_r[prectr] = x;
pre[x] = prectr++;
for(auto i : adjlist[x]){
if(i.first == par) continue;
preorder(i.first, x);
}
}
int ctr=0;
void dfs(int x, int par){ //
this is for euler (fenwick)
ctr++;
S[x] = ctr;
st[ctr][0] = pre[x];
for(auto i :
adjlist[x]){
if(i.first == par) continue;
add(ctr+1, i.second);
st[ctr][0] = pre[x];
dfs(i.first, x);
add(ctr+1, -i.second);
ctr++;
}
E[x] = ctr+1;
st[ctr][0] = pre[x];
}
// settle lca (rmq, st),
euler (fenwick)
int lca(int a, int b){
if(S[a] > S[b]) swap(a,b);
int len = S[b]-S[a]+1;
int k = 32-__builtin_clz(len)-1;
return pre_r[min(st[S[a]][k], st[S[b]-(1<<k)+1][k])];
}
void pre_st(){
for(int k = 1; k<=18; k++){
for(int i = 1; i<=2*n+9; i++){
assert(i+(1<<(k-1)) <= 500000);
st[i][k] = min(st[i][k-1],
st[i+(1<<(k-1))][k-1]);
}
}
}
int main(){
freopen("taqtree.txt", "r", stdin);
cin >> n;
for(int i = 0; i<n-1; i++){
int a,b,c;
cin >> a >> b >> c;
adjlist[a].push_back(pi(b,c));
adjlist[b].push_back(pi(a,c));
edgelist.push_back(edge(a,b,c));
}
preorder(1, -1);
dfs(1, -1);
pre_st();
cin >> q;
while(q--){
int a,b,c;
cin >> a >> b >> c;
if(a == 1){
// edit
b--;
int olda = edgelist[b].a, oldc = edgelist[b].c,
oldb = edgelist[b].b;
if(S[olda] > S[oldb]) swap(olda, oldb); //
olda is now the parent of oldb
add(S[oldb], -oldc);
add(E[oldb], oldc);
add(S[oldb], c);
add(E[oldb], -c);
edgelist[b].c
= c;
}else{
// change
if(S[b] > S[c]) swap(b,c);
int d = lca(b,c);
int ans = 0;
int td = d; if(S[td] > S[b]) swap(td, b);
ans += query(S[td]+1, S[b]);
td = d; if(S[td] > S[c]) swap(td, c); ans +=
query(S[td]+1, S[c]);
cout << ans << "\n";
}
}
}
Common Paths between Two
Paths (sherlockgraphs)
#include
<bits/stdc++.h>
using namespace std;
int n,m,q;
vector<int>
adjlist[100050];
bool visited[100050];
int p[100050][20];
int low[100050];
int depth[100050];
int pre[100050];
bool atp[100050];
int atppre[100050];
int ctr=0;
void dfs(int x){ // just for
ATB
visited[x] = true;
low[x] = ctr;
pre[x] = ctr;
ctr++;
for(auto i : adjlist[x]){
if(!visited[i]){
p[i][0]=x;
depth[i] = depth[x]+1;
dfs(i);
if(low[i]>pre[x]){
atp[i] = true;
}
low[x] = min(low[i], low[x]);
}else if(i != p[x][0]) low[x] = min(low[x], pre[i]);
}
}
void atpprecom(int x){
visited[x] = true;
for(auto i : adjlist[x]){
if(visited[i]) continue;
if(p[x][0] != i){
atppre[i] = atppre[x]+atp[i];
atpprecom(i);
}
}
}
void tkd(){
for(int k = 1; k<20; k++){
for(int i = 1; i<=n; i++){
if(p[i][k-1] != -1){
p[i][k] = p[p[i][k-1]][k-1];
}else p[i][k] = -1;
}
}
}
int lca(int a, int b){
if(depth[a]<depth[b]) swap(a,b);
for(int k = 19; k>=0; k--){
if(p[a][k] != -1 and depth[p[a][k]] >= depth[b])
a=p[a][k];
}
if(a==b) return a;
for(int k = 19; k>=0; k--){
if(p[a][k] != p[b][k]) a=p[a][k],b=p[b][k];
}
return p[a][0];
}
int dist(int a, int b){
return atppre[a] + atppre[b] - 2*atppre[lca(a,b)];
}
int inter(int a, int b, int
c, int d){
// a and c are the lcas
int ans = 0;
int ac = lca(a,c);
int bd = lca(b,d);
if(ac != a and ac != c) return 0; // disjoint paths
else if(ac == a){
// a is acestor of c (c stems)
if(lca(bd, c) == bd) return 0;
else ans = dist(bd, c);
}else{
// c is acestor of a
if(lca(bd, a) == bd) return 0;
else ans = dist(bd, a);
}
return ans;
}
int main(){
cin >> n >> m >> q;
for(int i = 0; i<m; i++){
int a,b;
cin >> a >> b;
adjlist[a].push_back(b);
adjlist[b].push_back(a);
}
depth[1] = 1;
dfs(1);
tkd();
memset(visited, false, sizeof visited);
atpprecom(1);
while(q--){
int a,b,c,d;
cin >> a >> b >> c >> d;
// join node a and b
// output path from c to d
int ans = 0;
int u = lca(a,b), v = lca(c,d);
ans = inter(u, a, v, c) + inter(u, b, v, c) + inter(u,
a, v, d) + inter(u, b, v, d);
cout << dist(c, d) - ans << "\n";
}
}
Heavy Light Decomposition
(grassplant)
#include
<bits/stdc++.h>
using namespace std;
typedef int ll;
// now a fenwick -.-
struct node{
vector<int> fw, fw2; // note this is 1 indexed, queries
are built to be 0 indexed
int s;
node(){}
node(int sz){ s = sz; fw.resize(sz+2); fw2.resize(sz+2); }
int query1(int x){
x++;
int ans = 0;
for(;x;x-=x&(-x)) ans+=fw[x];
return ans;
}
int query2(int x){
x++;
int ans = 0;
for(;x;x-=x&(-x)) ans+=fw2[x];
return ans;
}
void update1(int x, int v){
x++;
for(;x<=s;x+=x&(-x)) fw[x]+=v;
}
void update2(int x, int v){
x++;
for(;x<=s;x+=x&(-x)) fw2[x]+=v;
}
int point_query(int x){
return query1(x) * x + query2(x);
}
int range_query(int x, int y){
return point_query(y) - point_query(x-1);
}
void range_add(int x, int y, int v){
update1(x, v);
update1(y+1, -v);
update2(x, -(x-1)*v);
update2(y+1, y*v);
}
};
vector< node* > seg;
ll n, q;
struct treenode{
ll par, chain, depth, size, pos, weight;
// pos is position in chain it is in
// chain is the chain it is in
treenode(){ par = chain = depth = size = pos = weight = 0; }
} nodes[100050]; // struct to
contain a node
vector<ll>
adjlist[100050]; // adjacency list
ll segroot[100050],
segsize[100050]; // segroot[chain] = root of that segment, segsize[chain] =
size of that segment
void dfs_size(ll x, ll p){ //
for hld, calculate sizes , and a bunch of other stuff
nodes[x].size = 1;
for(auto i : adjlist[x]){
if(i == p) continue;
nodes[i].weight = 0;
nodes[i].par = x;
nodes[i].depth = nodes[x].depth + 1;
dfs_size(i, x);
nodes[x].size += nodes[i].size;
}
}
ll curchain = 0;
void hld(ll x, ll p){ // HLD
nodes[x].chain = curchain;
segsize[nodes[x].chain] = max(segsize[nodes[x].chain],
nodes[x].pos+1);
ll largest = 0, largest_size = 0;
for(auto i : adjlist[x]){
if(i == p) continue;
if(nodes[i].size >= largest_size) largest = i,
largest_size = nodes[i].size;
}
if(largest == 0) return;
// curchain remains at curchain
nodes[largest].pos = nodes[x].pos+1;
hld(largest, x);
for(auto i : adjlist[x]){
if(i == p or i == largest) continue;
curchain++; // curchain should only be the number of
light edges... but it reaches up to 100K
segroot[curchain] = i; // root of new chain
nodes[i].pos = 0; // root of new chain
hld(i, x);
}
}
ll lca(ll a, ll b){
if(a == b) return a;
ll ac = nodes[a].chain;
ll bc = nodes[b].chain;
if(ac == bc){
return nodes[a].depth < nodes[b].depth ? a : b;
}
ll ra = segroot[ac];
ll rb = segroot[bc];
if(nodes[ra].depth > nodes[rb].depth) return
lca(nodes[ra].par, b);
else return lca(a, nodes[rb].par);
}
ll query(ll a, ll b){ // b is
the ancestor
if(nodes[a].chain == nodes[b].chain){
if(nodes[b].pos+1 <= nodes[a].pos) return
seg[nodes[b].chain]->range_query(nodes[b].pos+1, nodes[a].pos);
return 0;
}
return query(nodes[segroot[nodes[a].chain]].par, b) +
seg[nodes[a].chain]->range_query(0, nodes[a].pos);
}
void update(ll a, ll b){ // b
is ancestor
if(nodes[a].chain == nodes[b].chain){
if(nodes[b].pos+1 <= nodes[a].pos)
seg[nodes[b].chain]->range_add(nodes[b].pos+1, nodes[a].pos, 1);
return;
}else{
seg[nodes[a].chain]->range_add(0,nodes[a].pos,1);
update(nodes[segroot[nodes[a].chain]].par, b);
}
}
void printchains(){
printf("Chains:\n");
for(ll i = 0; i<=curchain; i++){
printf("%d : ", i);
for(ll j = 0; j<segsize[i]; j++){
printf("%d ",
seg[i]->range_query(j,j));
}
printf("\n");
}
printf("\n");
}
int main(){
freopen("grassplant.1.2.in", "r", stdin);
cin >> n >> q;
for(ll i = 0; i<n-1; i++){
ll a,b; cin >> a >> b;
adjlist[a].push_back(b);
adjlist[b].push_back(a);
}
dfs_size(1, -1);
hld(1, -1);
for(ll i = 0; i<=curchain; i++) seg.push_back(new
node(segsize[i]));
while(q--){
ll a,b;
char qtype; cin >> qtype >> a >> b;
if(qtype == 'P'){ // plant
update(a, lca(a,b));
update(b, lca(a,b));
//printchains();
}else{ // query
cout << query(a, lca(a,b)) + query(b,
lca(a,b)) << "\n";
}
}
//for(ll i = 1; i<=n; i++) printf("%d : %d %d\n",
i, nodes[i].chain, nodes[i].pos);
}
Easy HLD (grassplant)
#include
<bits/stdc++.h>
using namespace std;
int n,q,t=1;
int fw1[100050], fw2[100050],
size[100050], s[100050], e[100050], nxt[100050], rs[100050];
vector<int>
adjlist[100050];
int depth[100050],
par[100050];
void update1(int p, int
newv){
for(;p<=100000;p+=p&(-p)) fw1[p] += newv;
}
void update2(int p, int
newv){
for(;p<=100000;p+=p&(-p)) fw2[p] += newv;
}
void range_update(int x, int
y, int v){
update1(x, v);
update1(y+1, -v);
update2(x, -(x-1)*v);
update2(y+1, y*v);
}
int query1(int p){
int ans = 0;
for(;p;p-=p&(-p)) ans+=fw1[p];
return ans;
}
int query2(int p){
int ans = 0;
for(;p;p-=p&(-p)) ans+=fw2[p];
return ans;
}
int query(int x){
return query1(x)*x + query2(x);
}
int range_query(int x, int
y){
return query(y) - query(x-1);
}
void dfs_size(int x, int p){
size[x] = 1;
for(auto &i : adjlist[x]){
if(i != p){
depth[i] = depth[x]+1;
par[i] = x;
dfs_size(i, x);
size[x] += size[i];
if(size[i] >= size[adjlist[x][0]]) swap(i,
adjlist[x][0]);
}
}
}
void hld(int x, int p){
rs[t] = x; // reverse start
s[x] = t++;
for(auto i : adjlist[x]){
if(i != p){
nxt[i] = (i == adjlist[x][0] ? nxt[x] : i);
hld(i, x);
}
}
e[x] = t;
}
int lca(int a, int b){
if(nxt[a] == nxt[b]) return depth[a] < depth[b] ? a : b; //
same chain, check depth
if(depth[par[nxt[a]]] < depth[par[nxt[b]]]) return lca(a,
par[nxt[b]]); // bring b up if a is higher
else return lca(par[nxt[a]], b); // else bring a up
}
void grow(int a, int b){
assert(b == lca(a, b));
while(nxt[a] != nxt[b]){
range_update(s[nxt[a]], s[a], 1);
a = par[nxt[a]];
}
if(s[b]+1 <= s[a]) range_update(s[b]+1, s[a], 1);
}
int ask(int a, int b){
assert(b == lca(a,b));
int ans = 0;
while(nxt[a] != nxt[b]){
ans += range_query(s[nxt[a]], s[a]);
a = par[nxt[a]];
}
if(s[b]+1 <= s[a]) ans+=range_query(s[b]+1, s[a]);
return ans;
}
int main(){
// freopen(".in", "r", stdin);
cin >> n >> q;
for(int i = 0; i<n-1; i++){
int a,b; cin >> a >> b;
adjlist[a].push_back(b);
adjlist[b].push_back(a);
}
par[1] = 0;
depth[1] = 1; // source of bug !!!! be careful!
nxt[1] = 1;
dfs_size(1, -1);
hld(1, -1);
while(q--){
int a,b;
char qtype; cin >> qtype >> a >> b;
if(qtype == 'P'){ // plant
grow(a, lca(a,b));
grow(b, lca(a,b));
}else{ // query
cout << ask(a, lca(a,b)) + ask(b,
lca(a,b)) << "\n";
}
}
// for(int i = 1; i<=n; i++) printf("%d %d %d %d
%d\n", s[i], e[i], nxt[i], depth[i], par[i]); printf("\n");
}
Modified PushRelabel with
Adjmat
typedef long long ll;
struct Edge{
ll cap, flow;
Edge(){cap = 0, flow = 0;}
Edge(int tar, ll capacity): cap(capacity),
flow(0) {}
ll amt() { return cap-flow; }
};
struct PushRelabel {
int N;
Edge G[105][105];
vector<int> height, cnt;
vector<bool> inq;
vector<ll> excess;
queue<int> q;
PushRelabel(int _N): N(_N), height(_N),
cnt(2*_N), inq(_N), excess(_N){
for(int
i = 0; i<=N; i++){
for(int
j = 0; j<=N; j++) G[i][j].cap = G[i][j].flow = 0;
}
}
void AddEdge(int a, int b, ll c) { //directed edge a -> b with capacity c
if (a == b) return;
G[a][b].cap += c;
}
void Enqueue(int x) {
if (inq[x] || excess[x] == 0) return;
inq[x] = 1;
q.push(x);
}
void Push(int x, Edge *e, Edge *re, int to)
{
int it = to;
if (height[x] <=
height[it]) return;
ll flow = min(excess[x], e->amt());
if (flow == 0) return;
e->flow += flow;
re->flow -=flow;
excess[x] -= flow;
excess[it] += flow;
Enqueue(it);
}
void Relabel(int x) {
if (excess[x] == 0) return;
--cnt[height[x]];
height[x] = 2*N;
for(int i = 0; i<=N; i++){
if(G[x][i].amt()
== 0) continue;
height[x] = min(height[x], height[i]+1);
}
++cnt[height[x]];
Enqueue(x);
}
void GapHeuristic(int g) {
for (int i = 0; i < N; ++i) {
if (height[i] >= g) {
--cnt[height[i]];
height[i] = max(height[i],
N+1);
++cnt[height[i]];
Enqueue(i);
}
}
}
void Discharge(int x) {
for(int
i = 0; i<=N; i++){
Push(x,
&G[x][i], &G[i][x], i);
if(excess[x]
== 0) return;
}
if (cnt[height[x]] == 1)
GapHeuristic(height[x]);
else Relabel(x);
}
ll MaxFlow(int S, int T) {
height[S] = N;
cnt[0] = N-1, cnt[N] = 1;
inq[S] = inq[T] = 1;
for(int i = 0; i<=N; i++){
excess[S]
+= G[S][i].cap;
Push(S,
&G[S][i], &G[i][S], i);
}
while (!q.empty()) {
int x = q.front();
q.pop(), inq[x] = 0;
Discharge(x);
}
return excess[T];
}
vector<int> MinCut(int S, int T) {
MaxFlow(S, T);
int split = N;
vector<int> ans;
for (int i = 1; i <= N; ++i) {
if (cnt[i] == 0) {
split = i;
break;
}
}
for (int i = 0; i < N; ++i) {
if (height[i] > split)
ans.push_back(i);
}
return ans;
}
};
Dinicճ
(untested, from https://gist.github.com/icyrhyme/3177630) O(EV^2)
#define MAXN 500
class Dinic {
int n, m,
head[MAXN], level[MAXN], s, t, work[MAXN];
struct
edge {
int
v, c, f, nxt;
edge()
{}
edge(int
v, int c, int f, int nxt): v(v), c(c), f(f), nxt(nxt) {}
}
e[MAXM];
bool
_bfs() {
static
int q[MAXN];
memset(level,
-1, sizeof(int) * n);
int
le = 0, ri = 0;
q[ri++]
= s;
level[s]
= 0;
while(le
< ri) {
for(int
k = q[le++], i = head[k]; i != -1; i = e[i].nxt) {
if(e[i].f
< e[i].c && level[e[i].v] == -1) {
level[e[i].v]
= level[k] + 1;
q[ri++]
= e[i].v;
}
}
}
return
(level[t] != -1);
}
int _dfs(int
u, int f) {
if(u == t)
return
f;
for(int&
i = work[u]; i != -1; i = e[i].nxt) {
if(e[i].f
< e[i].c && level[u] + 1 == level[e[i].v]) {
int
minf = _dfs(e[i].v, min(f, e[i].c - e[i].f));
if(minf
> 0) {
e[i].f
+= minf;
e[i
^ 1].f -= minf;
return
minf;
}
}
}
return
0;
}
public:
void
init(int nn, int src, int dst) {
n = nn;
s =
src;
t =
dst;
m = 0;
memset(head,
-1, sizeof(int) * n);
}
void
addEdge(int u, int v, int c, int rc) {
assert(u < n);
assert(v
< n);
e[m] = edge(v, c, 0, head[u]);
head[u]
= m++;
e[m]
= edge(u, rc, 0, head[v]);
head[v]
= m++;
assert(m
< MAXM);
}
int
maxFlow() {
int
ret = 0;
while(_bfs())
{
memcpy(work,
head, sizeof(int) * n);
while(true)
{
int
delta = _dfs(s, INF);
if(delta
== 0)
break;
ret
+= delta;
}
}
return
ret;
}
};
DP
LIS O(NlogN)
vector<int> lis;
int main() {
for(int i = 0; i<n; i++){
if(lis.empty() || A[i] > lis.back())
lis.push_back(A[i]);
else *lower_bound(lis.begin(), lis.end(), A[i]) = A[i];
// dp[i] = upper_bound(lis.begin(), lis.end(), A[i]) - lis.begin();
}
cout << lis.size();
}
LIS with Parent Tracking
(poklon)
#include
<bits/stdc++.h>
// *non-decreasing variant
using namespace std;
int n;
typedef pair<int, int>
pi;
pi A[100050];
int dp[100050];
int main(){
freopen("poklon.txt",
"r", stdin);
cin >> n;
for(int i=0; i<n; i++){
cin >> A[i].first >> A[i].second;
}
sort(A, A+n, [](pi a, pi b){ return (a.second==b.second and
a.first<b.first) or a.second > b.second; });
vector<pi> lis; // value, idx from
for(int i = 0; i<n; i++){
int cur = A[i].first;
if(lis.empty() or lis.back().first <= cur){
if(lis.empty()) dp[i] = -1; else dp[i] =
lis.back().second;
lis.push_back(pi(cur, i));
}else{
auto it = lower_bound(lis.begin(), lis.end(),
pi(cur, INT_MAX));
*it = pi(cur, i);
if(it!=lis.begin()) dp[i] = (*prev(it)).second;
else dp[i] = -1;
}
}
cout << lis.size() << endl;
int cur = lis.back().second;
vector<pi> v;
while(cur != -1){
v.push_back(A[cur]);
cur = dp[cur];
}
reverse(v.begin(), v.end());
for(auto i : v) cout << i.first << " "
<< i.second << "\n";
}
#include <bits/stdc++.h>
using namespace std;
int n;
typedef pair<int, int>
pi;
pi A[100050];
int p[100050];
bool cmp(int idx, int val){
return A[idx].first <= val;
}
int main(){
// freopen("poklon.txt", "r", stdin);
cin >> n;
for(int i = 0; i<n; i++) cin >> A[i].first >>
A[i].second;
sort(A, A+n, [](pi a, pi b){ return a.second == b.second ?
a.first < b.first : a.second > b.second; });
vector<int> lis;
for(int i = 0; i<n; i++){
int cur = A[i].first;
if(lis.empty() or A[lis.back()].first <= cur){ //
non decreasing
p[i] = lis.empty() ? -1 : lis.back();
lis.push_back(i);
}else{
int loc = lower_bound(lis.begin(), lis.end(),
cur, cmp) - lis.begin();
p[i] = loc == 0 ? -1 : lis[loc-1];
lis[loc] = i;
}
}
cout << lis.size() << endl;
int cur = lis.back();
vector<int> v;
while(cur != -1){
v.push_back(cur);
cur = p[cur];
}
reverse(v.begin(), v.end());
for(auto i : v) cout << A[i].first << "
" << A[i].second << "\n";
}
Maxsum O(N)
int A[N], maxsum[N];
int ans = maxsum[0] = A[0];
for (int i = 1; i < N;
++i) {
maxsum[i] = max(maxsum[i-1] + A[i], A[i]);
ans = max(ans, maxsum[i]);
}
int A[N];
int ans = A[0], cursum =
A[0];
for (int i = 1; i < N;
++i) {
if (cursum < 0) cursum = 0;
cursum += A[i];
ans = max(ans, cursum);
}
0-1 Knapsack (coinbag) O(NW)
#include
<bits/stdc++.h>
using namespace std;
int x, best[505][505];
int W[505], V[505];
int w;
int main(){
scanf("%d %d", &x, &w);
for(int i = 1; i<=x; i++){
scanf("%d %d", &W[i],
&V[i]);
}
memset(best, 0 , sizeof best);
for(int j = 1; j<=x; j++){
for(int n = 0; n<=w; n++){ // go from W[j] to w for faster
best [j][n] = best[j-1][n];
if(n>=W[j]) best[j][n] =
max(best[j][n], best[j-1][n-W[j]] + V[j]);
if(n > 0) best[j][n] =
max(best[j][n-1], best[j][n]);
}
}
printf("%d", best[x][w]);
}
0-1 Knapsack With Repeated
Items (CS3233 Qn) O(NWlogN)
#include
<bits/stdc++.h>
using namespace std;
typedef unsigned long long
ll;
ll S, N;
typedef pair<ll, ll>
pi;
typedef pair<pi, ll>
iii;
vector<iii> items;
ll dp[10050];
int main(){
while(cin >> S >> N){
ll addon = 0;
if(S == 0 and N == 0) break;
items.clear();
memset(dp, 0, sizeof dp);
for(int i = 0; i<N; i++){
ll v,w,k;
cin >> v >> w >> k;
if(w == 0){
addon += v*k;
continue;
}
int a=0;
while(k >= (1<<a)){
items.push_back(iii(pi(v,w),
(1<<a)));
k -= 1<<a;
a++;
}
if(k != 0) items.push_back(iii(pi(v,w), k));
}
for(auto i : items){
int cnt = i.second;
for(int k = S; k>=cnt*i.first.second; k--){
dp[k] = max(dp[k-1], dp[k]);
dp[k] = max(dp[k],
dp[k-cnt*i.first.second] + cnt*i.first.first);
}
}
cout << dp[S]+addon << "\n";
}
}
Unbounded Knapsack (untested
from geeksforgeeks)
int unboundedKnapsack(int W,
int n, int val[], int wt[])
{
// dp[i] is going to store maximum value
// with knapsack capacity i.
int dp[W+1];
memset(dp, 0, sizeof dp);
int ans = 0;
//
Fill dp[] using above recursive formula
for (int i=0; i<=W; i++)
for (int j=0; j<n; j++)
if (wt[j] <= i)
dp[i] = max(dp[i],
dp[i-wt[j]]+val[j]);
return dp[W];
}
0-1 Knapsack MITM (harddisk)
#include <bits/stdc++.h>
#define INF 10000000000000
using namespace std;
typedef long long ll;
ll n, c;
typedef pair<ll, ll>
pi;
pi A[45];
ll static_max[1100000];
pi one[1100000];
int main(){
freopen("input.txt",
"r", stdin);
cin >> n >> c;
for(int i = 0; i<n; i++) cin >> A[i].first >>
A[i].second;
ll firsthalf = n/2; //
note in actual solution its n/2-1 (to reduce memory)
for(int i = 0; i<(1<<firsthalf); i++){
ll value = 0, weight = 0;
for(int j = 0; j<firsthalf; j++){
if((1<<j) & i){
value += A[j].second;
weight += A[j].first;
}
}
one[i] = pi(weight, value);
}
sort(one, one+(1<<firsthalf));
// for(int i = 0; i<(1<<firsthalf); i++) printf("%d:
%d %d\n", i, one[i].first, one[i].second);
static_max[0] = one[0].second;
for(int i = 1; i<(1<<firsthalf); i++){
static_max[i] = max(static_max[i-1], one[i].second);
}
ll ans = 0;
for(int i = 0; i<(1<<(n-firsthalf)); i++){
ll value = 0, weight = 0;
for(int j = 0; j<n-firsthalf; j++){
if((1<<j) & i){
value += A[j+firsthalf].second;
weight += A[j+firsthalf].first;
}
}
int idx = upper_bound(one, one+(1<<firsthalf),
pi(c-weight, INF))-one-1;
if(idx < 0) continue;
ans = max(ans, static_max[idx] + value);
}
cout << ans;
}
Coin Change (mincoins)
(moneychanger)
#include
<bits/stdc++.h>
using namespace std;
int N, V, coins[10001],
value[10001];
int main()
{
cin >> N >> V;
for(int i = 0; i < N; i++)
{
cin >> coins[i];
}
value[0] = 0;
for(int i = 1; i<=V; i++){
value[i] = INT_MAX;
for(int j = 0; j<N; j++){
if(i>=coins[j] and
value[i-coins[j]]!=INT_MAX)
value[i] =
min(value[i],value[i-coins[j]]+1);
}
}
if(value[V] == INT_MAX) cout << -1;
else
cout<<value[V];
}
Coin Change (ways)
#include
<bits/stdc++.h>
using namespace std;
int n,v, coins[55],
ways[10050]; //value, index of minimum coin
int main(){
scanf("%d %d", &n, &v);
for(int i = 1; i<=n; ++i)
scanf("%d", &coins[i]);
ways[0] = 1;
for(int i = 1; i<=n; i++){
for(int j = 1; j<=v; j++){
if(j>=coins[i])
ways[j]+=ways[j-coins[i]];
ways[j]%=13371337;
}
}
cout << ways[v] % 13371337;
}
2D Maxsum (orchard)
#include
<bits/stdc++.h>
using namespace std;
const int maxh = 155, maxw =
100050;
int h, w;
int grid[maxh][maxw];
int ss[maxh][maxw];
int query(int x, int y1, int
y2){
return ss[y2][x] - ss[y1-1][x];
}
int ctr = 0;
int main(){
scanf("%d %d", &h, &w);
for(int i = 1; i<=h; ++i){
for(int j = 1; j<=w; ++j){
int hi;
scanf("%d", &hi);
if (hi == 0){
grid[i][j] = -1;
}else{
ctr++;
grid[i][j] = 1;
}
}
}