498C - Array and Operations - CodeForces Solution

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

#ifdef local
#include"debug/debug.cpp"
#else
#define dbg(...)
#endif


#define test_case int test_cases;\
    cin>>test_cases;\
    for(i = 1; i<=test_cases;++i)

#define lu(i,l, r) for(int i = l; i < r; ++i)
#define ld(i, r, l) for(int i = r; i >= l; --i)
#define in_c(A, l, r) for(int input_iter = l; input_iter < r; ++input_iter) cin >> A[input_iter]

#define Max_heap priority_queue<int>
#define Min_heap priority_queue<int, vector<int>, greater<int>>

#define precision cout<<std::fixed<<setprecision(25);\
    cerr<<std::fixed<<setprecision(25)
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define all(A) (A).begin(),(A).end()
#define kick "Case #"<<test<<": "
#define endl "\n"
typedef long long ll;

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int mod = 1e9 + 7;

ll ceil(ll a, ll b) {
    return (a + b - 1) / b;
}

vector<int> d4x{0, 0, 1, -1};
vector<int> d4y{ -1, 1, 0, 0};
vector<int> d8x{0 , 0, 1, -1, 1, 1, -1, -1};
vector<int> d8y{1, -1, 0, 0, -1, 1, 1, -1};

class EdmondsKarp {
	static const int N = 1000; // max number of nodes

	int residual[N][N];

	vector<int> graph[N];

public:

	void reset() {
		memset(residual, 0, N * N);
	}

	EdmondsKarp() {
		reset();
	}

	EdmondsKarp(vector<pair<int,int>> graph[], int n) {
		reset();

		lu(i, 0, n) {
			addEdges(i, graph[i]);
		}
	}

	EdmondsKarp(vector<vector<pair<int,int>>> &graph) {
		reset();

		lu(i, 0, graph.size()) {
			addEdges(i, graph[i]);
		}
	}

	void addEdge(int s, int d, int c) {
		graph[s].push_back(d);
		residual[s][d] = c;
        residual[d][s] = 0;
		graph[d].push_back(s);
	}

	void addEdges(int s, vector<pair<int,int>> &ds) {
		for(pair<int,int> &iter : ds) {
			addEdge(s, iter.first, iter.second);
		}
	}

	int getFlow(int s, int t, vector<int> &parent) {

		fill(all(parent), -1);

		parent[s] = -2;


		queue<pair<int,int>> q;

		q.push({s, INT_MAX});

		while(!q.empty()) {
			pair<int,int> nodePair = q.front();
			q.pop();

			int node = nodePair.first; 
			int currentFlow = nodePair.second;

			if(node == t) {
				return currentFlow;
			}

			for(int neighbour : graph[node]) {
				if(parent[neighbour] == -1 && residual[node][neighbour] > 0) {
					parent[neighbour] = node;
					q.push({neighbour, min(currentFlow, residual[node][neighbour])});
				}
			}
		}

		return 0;
	}

	ll getMaxFlow(int s, int t) {
		vector<int> parent(N, -1);

		ll flow = 0;
		int currentFlow;

		while(currentFlow = getFlow(s, t, parent)) {
            dbg("flow", currentFlow);
			flow += currentFlow;

			int parNode = parent[t];
			int currNode = t;

			while(parNode != -2) {
                dbg(parNode);
				residual[parNode][currNode] -= currentFlow;

				residual[currNode][parNode] += currentFlow;

				currNode = parNode;
				parNode = parent[parNode];
			}
		}

		return flow;
	}
};

vector<pair<int,int>> getPrimes(int n) {
    vector<pair<int,int>> ans;

    int i = 2;

    for(i = 2; i*1ll* i <= n; ++i) {
        int cnt = 0;

        while(n%i == 0) {
            cnt++;
            n/=i;
        }

        if(cnt) {
            ans.push_back({i, cnt});
        }
    }

    if(n != 1) {
        ans.push_back({n, 1});
    }
    return ans;
}

void solve(int test) {
    int n, m;
    cin>>n>>m;
    vector<int> A(n);
    in_c(A, 0, n);

    EdmondsKarp maxFlow;

    map<int,map<int,pair<int,int>>> nodes;

    int start = 999, end = 998;
    int index =1;

    lu(i, 0, n) {
        vector<pair<int,int>> primes = getPrimes(A[i]);

        for(auto iter : primes) {
            nodes[i][iter.first] = {
                index++, iter.second
            };
        }
    }

    vector<bool> added(n, false);

    lu(i, 0, m) {
        int x, y;
        cin>>x>>y;
        --x;--y;
        if(x&1) {
            swap(x, y);
        }
        if(!added[x]) {
            added[x] = true;
          
            for(auto iter : nodes[x]) {
                maxFlow.addEdge(start, iter.second.first, iter.second.second);
                // dbg(start, iter.second.first);
            }
        }

        if(!added[y]) {
            added[y] = true;
            for(auto iter : nodes[y]) {
                maxFlow.addEdge(iter.second.first, end, iter.second.second);
                // dbg(iter.second.first, end);
            }
        }

        for(auto iter: nodes[x]) {
            maxFlow.addEdge(iter.second.first, nodes[y][iter.first].first, 34);
            // dbg(iter.second.first, nodes[y][iter.first].first);
        }
    }

    cout<<maxFlow.getMaxFlow(start, end);
}

int main() {
    precision;
    fastio;
    int i = 1;
    // test_case
    solve(i);
    return 0;
}