Task: | Download Speed |
Sender: | paulschulte |
Submission time: | 2024-10-16 15:59:38 +0300 |
Language: | C++ (C++17) |
Status: | READY |
Result: | WRONG ANSWER |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.00 s | details |
#2 | ACCEPTED | 0.00 s | details |
#3 | ACCEPTED | 0.00 s | details |
#4 | ACCEPTED | 0.00 s | details |
#5 | WRONG ANSWER | 0.00 s | details |
#6 | ACCEPTED | 0.01 s | details |
#7 | ACCEPTED | 0.01 s | details |
#8 | ACCEPTED | 0.00 s | details |
#9 | ACCEPTED | 0.00 s | details |
#10 | ACCEPTED | 0.00 s | details |
#11 | WRONG ANSWER | 0.00 s | details |
#12 | ACCEPTED | 0.00 s | details |
Code
// ~/.vim/cpp_template.cpp#include <bits/stdc++.h>#include <iostream>#include <vector>#include <algorithm>#include <string>#include <limits>#define REP(i,a,b) for (int i = a; i < b; i++)// Type Aliases for 1D and 2D vectors with initialization#define vi(n, val) vector<int>(n, val) // 1D vector of ints with size n, initialized to val#define vll(n, val) vector<long long>(n, val) // 1D vector of long longs with size n, initialized to val#define ll long long#define vvi(n, m, val) vector<vector<int>>(n, vector<int>(m, val)) // 2D vector of ints (n x m), initialized to val#define vvll(n, m, val) vector<vector<long long>>(n, vector<long long>(m, val)) // 2D vector of long longs (n x m), initialized to val#define LL_INF std::numeric_limits<long long int>::max()#define INF std::numeric_limits<int>::max()using namespace std;template <typename T>void pV(const std::vector<T>& vec, const std::string& label = "Vector") {std::cout << label << ": [ ";for (const auto& elem : vec) {std::cout << elem << " ";}std::cout << "]" << std::endl;}void dfs(int s, vector<bool> *visited, vector<int> (*adj)[]) {if ((*visited)[s]) return;(*visited)[s] = true;// process node sfor (auto u: (*adj)[s]) {dfs(u, visited, adj);}}/*// DEPTH-FRIRST-SEARCHvector<int> adj[N];vector<bool> visited(N, false);int u, v;for(int i = 0; i < M;i++){cin >> u >> v;u--;v--;adj[u].push_back(v);adj[v].push_back(u);}*/vector<long long> dijkstra(int N, int x, vector<vector<pair<int,int>>> *adj){vector<bool> processed(N, false);vector<long long> distance(N, LL_INF);priority_queue<pair<long long,int>> q;//for (int i = 1; i <= n; i++) distance[i] = INF;distance[x] = 0;q.push({0,x});while (!q.empty()) {int a = q.top().second; q.pop();if (processed[a]) continue;processed[a] = true;for (auto u : (*adj)[a]) {int b = u.first, w = u.second;if (distance[a]+w < distance[b]) {distance[b] = distance[a]+w;q.push({-distance[b],b});}}}return distance;}/*DIJKSTRA//vector<vector<pair<int,int>>> adj(N, vector<pair<int, int>>(N));*/const int MAX_N = 500;bool bfs(int s, int t, vector<vector<int>>& capacity, vector<int>& parent, vector<vector<int>>& adj) {int n = capacity.size();vector<bool> visited(n, false);queue<int> q;q.push(s);visited[s] = true;parent[s] = -1;while(!q.empty()) {int u = q.front();q.pop();for(int v : adj[u]) {if(!visited[v] && capacity[u][v] > 0) {parent[v] = u;if(v == t) {return true;}visited[v] = true;q.push(v);}}}return false;}long long edmondsKarp(int s, int t, vector<vector<int>>& capacity, vector<vector<int>>& adj) {int u, v;int n = capacity.size();vector<int> parent(n);long long maxFlow = 0;while(bfs(s, t, capacity, parent, adj)) {int pathFlow = INT_MAX;for(v = t; v != s; v = parent[v]) {u = parent[v];pathFlow = min(pathFlow, capacity[u][v]);}for(v = t; v != s; v = parent[v]) {u = parent[v];capacity[u][v] -= pathFlow;capacity[v][u] += pathFlow;}maxFlow += pathFlow;}return maxFlow;}int main() {ios::sync_with_stdio(0);cin.tie(0);// Your code starts hereint n, m;cin >> n >> m;vector<vector<int>> capacity(n + 1, vector<int>(n + 1, 0));vector<vector<int>> adj(n + 1);for (int i = 0; i < m; i++) {int a, b, c;cin >> a >> b >> c;capacity[a][b] += c;adj[a].push_back(b);adj[b].push_back(a);}cout << edmondsKarp(1, n, capacity, adj) << endl;return 0;}
Test details
Test 1
Verdict: ACCEPTED
input |
---|
4 3 1 2 5 2 3 3 3 4 6 |
correct output |
---|
3 |
user output |
---|
3 |
Test 2
Verdict: ACCEPTED
input |
---|
4 5 1 2 1 1 3 1 2 3 1 2 4 1 ... |
correct output |
---|
2 |
user output |
---|
2 |
Test 3
Verdict: ACCEPTED
input |
---|
4 5 1 2 1000000000 1 3 1000000000 2 3 1 2 4 1000000000 ... |
correct output |
---|
2000000000 |
user output |
---|
2000000000 |
Test 4
Verdict: ACCEPTED
input |
---|
2 1 2 1 100 |
correct output |
---|
0 |
user output |
---|
0 |
Test 5
Verdict: WRONG ANSWER
input |
---|
2 1000 1 2 1000000000 1 2 1000000000 1 2 1000000000 1 2 1000000000 ... |
correct output |
---|
1000000000000 |
user output |
---|
0 |
Test 6
Verdict: ACCEPTED
input |
---|
500 998 1 2 54 1 3 59 1 4 83 2 5 79 ... |
correct output |
---|
60 |
user output |
---|
60 |
Test 7
Verdict: ACCEPTED
input |
---|
500 998 1 2 530873053 1 3 156306296 1 4 478040476 3 5 303609600 ... |
correct output |
---|
1093765123 |
user output |
---|
1093765123 |
Test 8
Verdict: ACCEPTED
input |
---|
2 1 1 2 1 |
correct output |
---|
1 |
user output |
---|
1 |
Test 9
Verdict: ACCEPTED
input |
---|
4 5 1 2 3 2 4 2 1 3 4 3 4 5 ... |
correct output |
---|
6 |
user output |
---|
6 |
Test 10
Verdict: ACCEPTED
input |
---|
4 5 1 2 1 1 3 2 3 2 1 2 4 2 ... |
correct output |
---|
3 |
user output |
---|
3 |
Test 11
Verdict: WRONG ANSWER
input |
---|
10 999 1 2 1000000000 1 2 1000000000 1 2 1000000000 1 2 1000000000 ... |
correct output |
---|
111000000000 |
user output |
---|
0 |
Test 12
Verdict: ACCEPTED
input |
---|
7 9 1 2 1 1 3 1 1 4 1 2 5 1 ... |
correct output |
---|
2 |
user output |
---|
2 |