CSES - Aalto Competitive Programming 2024 - wk7 - Wed - Results
Submission details
Task:Airport
Sender:aalto2024h_005
Submission time:2024-10-23 17:25:26 +0300
Language:C++ (C++11)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3ACCEPTED0.00 sdetails
#4ACCEPTED0.00 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.01 sdetails
#7ACCEPTED0.01 sdetails
#8ACCEPTED0.01 sdetails
#9ACCEPTED0.01 sdetails
#10ACCEPTED0.01 sdetails
#11ACCEPTED0.00 sdetails
#12ACCEPTED0.00 sdetails
#13ACCEPTED0.00 sdetails

Code

#include <iostream>
#include <limits.h>
#include <queue>
#include <string.h>
#include <vector>
using namespace std;
bool bfs(vector<vector<long long>>& rGraph, int s, int t, vector<long long>& parent)
{
int V = rGraph.size();
vector<bool> visited(V,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 = 0; v < V; v++) {
if (visited[v] == false && rGraph[u][v] > 0) {
if (v == t) {
parent[v] = u;
return true;
}
q.push(v);
parent[v] = u;
visited[v] = true;
}
}
}
return false;
}
long long fordFulkerson(vector<vector<long long>> graph, int s, int t)
{
int u, v;
int V = graph.size();
vector<vector<long long>> rGraph(V,vector<long long>(V));
for (u = 0; u < V; u++)
for (v = 0; v < V; v++)
rGraph[u][v] = graph[u][v];
vector<long long> parent(V);
long long max_flow = 0;
while (bfs(rGraph, s, t, parent)) {
long long path_flow = LONG_LONG_MAX;
for (v = t; v != s; v = parent[v]) {
u = parent[v];
path_flow = min(path_flow, rGraph[u][v]);
}
for (v = t; v != s; v = parent[v]) {
u = parent[v];
rGraph[u][v] -= path_flow;
rGraph[v][u] += path_flow;
}
max_flow += path_flow;
}
return max_flow;
}
int main()
{
int n,m;
cin >> n >> m;
vector<vector<long long>> graph(2*n,vector<long long>(2*n,0));
for(int i=0; i< n; i++){
long long a;
cin >> a;
if(a==-1) graph[i][i+n]=LONG_LONG_MAX;
else graph[i][(i+n)]=a;
}
for(int i=0; i<m; i++){
int a,b;
cin >> a >> b;
graph[a-1+n][b-1]=LONG_LONG_MAX;
}
// for(int i=0; i< 2*n; i++){
// for(int l=0; l<2*n; l++){
// cout << graph[i][l] << " ";
// }
// cout << endl;
// }
cout << fordFulkerson(graph, 0, (2*n)-1) << endl;
}

Test details

Test 1

Verdict: ACCEPTED

input
10 20
-1 85 7 19 90 72 11 46 65 -1
6 7
9 7
8 4
...

correct output
7

user output
7

Test 2

Verdict: ACCEPTED

input
10 20
-1 80 77 57 77 95 63 98 30 -1
6 7
8 9
7 8
...

correct output
30

user output
30

Test 3

Verdict: ACCEPTED

input
10 20
-1 63 16 42 62 70 9 94 68 -1
10 9
6 8
10 6
...

correct output
25

user output
25

Test 4

Verdict: ACCEPTED

input
10 20
-1 3 86 -1 32 34 9 50 -1 -1
6 7
7 8
9 2
...

correct output
3

user output
3

Test 5

Verdict: ACCEPTED

input
10 20
-1 43 38 -1 7 54 26 97 76 -1
3 9
9 10
6 7
...

correct output
76

user output
76

Test 6

Verdict: ACCEPTED

input
100 1000
-1 425576195 274150382 1021768...

correct output
6091126630

user output
6091126630

Test 7

Verdict: ACCEPTED

input
100 1000
-1 769953265 -1 389517741 2323...

correct output
769953265

user output
769953265

Test 8

Verdict: ACCEPTED

input
100 1000
-1 584988267 763129662 6781413...

correct output
1699511766

user output
1699511766

Test 9

Verdict: ACCEPTED

input
100 1000
-1 921671366 121044688 2933366...

correct output
1805833567

user output
1805833567

Test 10

Verdict: ACCEPTED

input
100 1000
-1 763842763 612011030 4532521...

correct output
3342235784

user output
3342235784

Test 11

Verdict: ACCEPTED

input
3 3
-1 1 -1
1 2
2 3
2 2

correct output
1

user output
1

Test 12

Verdict: ACCEPTED

input
3 4
-1 1 -1
1 2
1 2
2 3
...

correct output
1

user output
1

Test 13

Verdict: ACCEPTED

input
7 8
-1 1 1 1 1 1 -1
1 2
1 3
2 4
...

correct output
1

user output
1