Download Speed

input/code.cpp: In function 'void print_matrix(std::vector<std::vector<int> >, std::string)':
input/code.cpp:28:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for (int i = 0; i < in.size(); i++) {
      |                         ~~^~~~~~~~~~~
input/code.cpp:30:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |                 for (int j = 0; j < in[i].size(); j++) {
      |                                 ~~^~~~~~~~~~~~~~
input/code.cpp: In function 'void dfs(int, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&, std::vector<int>&)':
input/code.cpp:59:13: warning: unused variable 'a' [-Wunused-variable]
   59 |         int a = edges[u][0];
      |             ^

#include <climits>
#include <cmath>
#include <iostream>
#include <vector>
 
// Debug printing
#ifdef DEBUG
#define deb(fmt, args...) printf("DEBUG: %d: " fmt, __LINE__, ##args)
#else
#define deb(fmt, args...)
#endif
 
using namespace std;
using ll = long long;
 
void print_array(vector<int> in, const string title = "Vector")
{
	cout << title << " [\n";
	for (const auto &el : in) {
		cout << el << " ";
	}
	cout << "\n] END\n";
}
 
void print_matrix(vector<vector<int> > in, const string title = "Matrix")
{
	cout << title << " [\n";
	for (int i = 0; i < in.size(); i++) {
		cout << "row " << i << ": ";
		for (int j = 0; j < in[i].size(); j++) {
			cout << in[i][j] << " ";
		}
		cout << "\n";
	}
	cout << "] END\n";
}
 
int target;
int found = true;
vector<int> path;
bool visited[500];
 
void dfs(int s, vector<vector<int> > &adj, vector<vector<int> > &edges,
	 vector<int> &path)
{
	if (found) {
		return;
	}
	if (visited[s]) {
		return;
	};
	visited[s] = true;
	if (s == target) {
		found = true;
		return;
	}
 
	for (auto u : adj[s]) {
        int a = edges[u][0];
        int b = edges[u][1];
        int c = edges[u][2];
        // deb("s: %d, a: %d, b: %d, c: %d\n", s, a, b, c);
        if (c > 0) {
            path.push_back(u);
            dfs(b, adj, edges, path);
            if (found) return;
            path.pop_back();
        }
	}
}
 
void find_cut(vector<int> &nodes)
{
	for (int i = 1; i < 501; i++) {
		if (visited[i])
			nodes.push_back(i);
	}
}
 
int main(int argc, char *argv[])
{
	int n, m;
	cin >> n >> m;
    target = n;
	// each edge is of form (a, b, c, i)
	vector<vector<int> > edges(m + 1, vector<int>(3));
	for (int i = 1; i < m + 1; i++) {
		cin >> edges[i][0] >> edges[i][1] >> edges[i][2];
	}
 
 
	// Add edges to adjacent structure
	// tuple contains target node, residual capacity and edge index
	// each element contains a vector of edges that are adjacent to the node
	vector<vector<int> > adj(n + 1, vector<int>());
	for (int j = 1; j < m + 1; j++) {
		adj[edges[j][0]].push_back(j);
		// adj[edges[j][1]].push_back(j);
	}
 
	// print_matrix(edges, "edges");
	// print_matrix(adj, "adjacent");
 
    int index = 0;
    int speed = 0;
	while (found) {
		found = false;
		for (int i = 0; i < n + 1; i++)
			visited[i] = false;
 
		path.clear();
		dfs(1, adj, edges, path);
        // print_array(path, "path");
		if (found) {
			// add stuff
			int residual = INT_MAX;
			// find residual capacity of the path
			for (auto e : path) {
				vector<int> edge = edges[e];
                // deb("ei: %d, c: %d\n", e, edge[2]);
                if (edge[2] < residual) residual = edge[2];
			}
            // deb("res: %d\n", residual);
            speed += residual;
 
			// update flows
			for (auto e : path) {
				if (e < 0) {
					edges[-e][2] += residual;
				} else {
					edges[e][2] -= residual;
				}
			}
		}
        index++;
	}
 
    cout << speed << "\n";
 
	return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: ACCEPTED

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: WRONG ANSWER