# GNUM giving TLE

I have implemented max flow using push relabel algorithm, and used the method described in the editorial for the problem GNUM, but still getting TLE. can any one say whats making it exceed the time limit?

here is my code: at ideone

``````#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define MAX 160100

int height[MAX], excess[MAX];
int s, t, N;

class Edge{
public:
int from, to, cap, flow, res_flow, index;

Edge(int from, int to, int cap, int flow, int res_flow, int index):
from(from),to(to),cap(cap),flow(flow),res_flow(res_flow),index(index){
}
};

vector<vector<Edge> > G;

void addEdge(int from, int to, int cap){
Edge ed(from, to, cap, 0, cap, G[to].size());
Edge ed_rev(to, from, 0, 0, 0, G[from].size());
G[from].pb(ed);
G[to].pb(ed_rev);
}

void initializePreflow(){
memset(height, 0, sizeof(height));
height[s] = N;
memset(excess, 0, sizeof(excess));
int v;
for(int i=0; i<G[s].size(); i++){
v = G[s][i].to;
G[s][i].flow = G[s][i].cap;
G[v][G[s][i].index].flow = -G[s][i].cap;

excess[v] = G[s][i].cap;
excess[s] -= G[s][i].cap;

G[s][i].res_flow = G[s][i].cap - G[s][i].flow;
G[v][G[s][i].index].res_flow = G[v][G[s][i].index].cap - G[v][G[s][i].index].flow;
}
}

void push(int u, int i){
int amt = min(excess[u], G[u][i].res_flow);
G[u][i].flow = G[u][i].flow + amt;
int v = G[u][i].to;
G[v][G[u][i].index].flow = -G[u][i].flow;
excess[u] = excess[u]-amt;
excess[v] = excess[v]+amt;
G[u][i].res_flow = G[u][i].cap - G[u][i].flow;
G[v][G[u][i].index].res_flow = G[v][G[u][i].index].cap - G[v][G[u][i].index].flow;
}

void displayG(){
for(int i=0;i<N;i++){
cout << i << ": ";
for(int j=0;j<G[i].size();j++){
cout << "-> (" << G[i][j].to << "," << G[i][j].cap << ") ";
}
cout << endl;
}
}

int maxFlow(int s, int t){
initializePreflow();
queue<int> q;
int active[N];
memset(active,0,sizeof(active));
for(int i=0;i<G[s].size();i++){
if(G[s][i].to != t){
q.push(G[s][i].to);
active[G[s][i].to] = 1;
}
}
int u,minimum;
while(q.size()!=0){
u = q.front();
//cout << "processing: " << u << "...\n";
minimum = -1;
for(int i=0; i<G[u].size() && excess[u]>0; i++){
int v = G[u][i].to;
if(G[u][i].res_flow>0){
if(height[u]>height[v]){
push(u,i);
if(!active[v] && v!=s && v!=t){
active[v] = 1;
q.push(v);
}
} else if(minimum==-1){
minimum = height[v];
} else{
minimum = min(minimum, height[v]);
}
}
}
if(excess[u]!=0)
height[u] = 1+minimum;
else{
active[u] = 0;
q.pop();
}
}
return excess[t];
/*
int tot_flow = 0;
for(int i=0; i<G[s].size();i++){
tot_flow += G[s][i].flow;
}
*/
}

vector<int> vA, primes;
vector<int> middle;
map<int,int> gL, gR;

const int limit = 31650; //sqrt(10^9)
const int max_factor = 10;
const int inf = 1000000000;
bool is_prime[limit+1];

int gcd(int a, int b){
if(b==0)
return a;
return gcd(b,a%b);
}

vector<int> factorize(int x){
vector<int> ret;
for(int i=0; i<primes.size() && primes[i]*primes[i]<=x; i++){
int d = primes[i];
if(x%d==0){
ret.pb(d);
middle.pb(d);
while(x%d==0){
x /= d;
}
}
}
if(x>1){
ret.pb(x);
middle.pb(x);
}
return ret;
}

void fillPrimes(){
memset(is_prime, true, sizeof(is_prime));
for(int i=2;i<=limit;i++){
if(is_prime[i]){
primes.pb(i);
for(int j=i*i; j<=limit;j+=i){
is_prime[j] = false;
}
}
}
}

int main(){

fillPrimes();
int tcs;
cin >> tcs;
while(tcs--){
int n;
cin >> n;

gL.clear(); gR.clear();
vA.clear();

int x;
for(int i = 0; i < n; i++){
cin >> x;
vA.push_back(x);
}

int g;
for(int j = 0; j < n; j++){
cin >> x;
for(int i = 0; i < n; i++){
if(vA[i] < x){ // Left
g = gcd(vA[i],x);
if(g > 1){
if(!gL.count(g)){
gL[g] = 0;
}
gL[g]++;
}
}
else if(vA[i] > x){ // Right
g = gcd(vA[i],x);
if(g > 1){
if(!gR.count(g)){
gR[g] = 0;
}
gR[g]++;
}
}
}
}

map<int,int>::const_iterator it, it2;
int id, id2;

vector<vector<int> > left_factors, right_factors;
middle.clear();

for(it = gL.begin(), id = 1; it != gL.end(); ++it, id++){
left_factors.pb(factorize(it->first)); //this also adds them to middle

}
for(it = gR.begin(), id = gL.size()+1;it != gR.end(); it++, id++){
right_factors.pb(factorize(it->first)); //this also adds them to middle
}

sort(middle.begin(), middle.end()); // sorts the middle nodes
middle.erase( unique(middle.begin(), middle.end()), middle.end() ); // removes duplicates and erases the space

G.clear();
N = gL.size()+middle.size()+gR.size()+2;
G.resize(N);
int source = 0, target = N-1;
s = source;
t = target;
int sz,k, ind;
for(it = gL.begin(), id = 1, ind = 0; it != gL.end(); ++it, id++, ind++){
sz = left_factors[ind].size();
for(int j=0;j<sz;j++){
k = lower_bound(middle.begin(),middle.end(),it->first)-middle.begin();
}
}

for(it = gR.begin(), id = gL.size()+middle.size()+1, ind = 0;it != gR.end(); it++, id++, ind++){
sz = right_factors[ind].size();
for(int j=0;j<sz;j++){
k = lower_bound(middle.begin(),middle.end(),it->first)-middle.begin();
}
}

//displayG();

cout << maxFlow(source, target) << endl;
}
return 0;
}
``````

Use fast I/O

EDIT: I’ve tried your code with scanf/printf and still TLE’d.

@caioaao >> i have used some part of your main code(to find distinct gcd values for left and right parts, bcoz it took me so long to learn and implement push-relabel algorithm). i also tried it using fast i/o which also TLEd.

I think that O(V^2*E) algo of push-relable TLEs in this problem, i later tried O(v^3) algo which was accepted.