— Dark mode

Aalto Competitive Programming 2025 - wk7 - Mon

Road blockade

  • Start: 2025-10-20 16:20:00
  • End: 2025-10-20 17:50:00
Submission details
Task:Road blockade
Sender:Dereden
Submission time:2025-10-20 17:29:39 +0300
Language:C++ (C++17)
Status:READY
Result:
Test results
testverdicttime
#10.00 sdetails
#20.00 sdetails
#30.00 sdetails
#40.00 sdetails
#50.00 sdetails
#60.00 sdetails
#70.00 sdetails
#80.00 sdetails
#90.00 sdetails
#100.00 sdetails
#110.00 sdetails
#120.00 sdetails
#130.00 sdetails
#140.00 sdetails
#150.00 sdetails
#160.00 sdetails
#170.00 sdetails
#180.00 sdetails
#190.00 sdetails
#200.00 sdetails
#210.00 sdetails
#220.00 sdetails
#230.00 sdetails
#240.00 sdetails
#250.00 sdetails
#260.00 sdetails
#270.00 sdetails
#280.00 sdetails
#290.00 sdetails
#300.00 sdetails
#310.00 sdetails
#320.00 sdetails
#330.00 sdetails
#340.00 sdetails
#350.00 sdetails
#360.00 sdetails
#370.00 sdetails
#380.00 sdetails
#390.00 sdetails
#400.00 sdetails
#410.00 sdetails
#420.00 sdetails
#430.00 sdetails
#440.00 sdetails
#450.00 sdetails
#460.00 sdetails
#470.00 sdetails
#480.00 sdetails
#490.00 sdetails
#500.00 sdetails
#510.00 sdetails
#520.00 sdetails
#530.00 sdetails
#540.00 sdetails
#550.00 sdetails
#560.00 sdetails
#570.00 sdetails
#580.00 sdetails
#590.00 sdetails
#600.00 sdetails
#610.00 sdetails
#620.00 sdetails
#630.00 sdetails
#640.00 sdetails
#650.00 sdetails
#660.00 sdetails
#670.00 sdetails
#680.00 sdetails
#690.00 sdetails

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:52:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |     freopen("input.txt", "r", stdin); // TODO: REMOVE THIS YOU STUPID ****
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <climits>

typedef long long ll;

using namespace std;

struct Edge {
    int to;
    ll cap;
    int rev;
    bool is_rev;
};

const ll INF = (1LL << 60);
vector<vector<Edge> > graph;
vector<bool> used;


ll dfs(int v, int t, ll f, ll delta) {
    if (v == t) return f;
    used[v] = true;
    for (auto &e: graph[v]) {
        if (!used[e.to] && e.cap >= delta) {
            ll pushed = dfs(e.to, t, min(f, e.cap), delta);
            if (pushed > 0) {
                e.cap -= pushed;
                graph[e.to][e.rev].cap += pushed;
                return pushed;
            }
        }
    }
    return 0;
}

void mark_reachable(int v, vector<char> &reach) {
    reach[v] = 1;
    for (auto &e: graph[v]) {
        if (e.cap > 0 && !reach[e.to]) {
            mark_reachable(e.to, reach);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    freopen("input.txt", "r", stdin); // TODO: REMOVE THIS YOU STUPID ****

    int n, m;
    cin >> n >> m;
    graph = vector<vector<Edge> >(n + 1);
    vector<pair<int, int>> edgesOrig;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        edgesOrig.push_back(make_pair(u, v));
        Edge a = {v, 1, (int) graph[v].size(), false};
        Edge b = {u, 0, (int) graph[u].size(), true};
        graph[u].push_back(a);
        graph[v].push_back(b);

        Edge c = {u, 1, (int) graph[u].size(), false};
        Edge d = {v, 0, (int) graph[v].size(), true};
        graph[v].push_back(c);
        graph[u].push_back(d);
    }

    int s = 1;
    int t = n;

    ll delta = 1;

    while (delta > 0) {
        while (true) {
            used.assign(n + 1, false);
            ll f = dfs(s, t, INF, delta);
            if (f == 0) break;
        }
        delta >>= 1;
    }

    vector<char> reach(n + 1, 0);
    mark_reachable(s, reach);

    vector<pair<int, int> > cut_edges;
    for (int u = 1; u <= n; ++u)
        if (reach[u]) {
            for (auto &e: graph[u]) {
                if (!e.is_rev && !reach[e.to]) {
                    cut_edges.emplace_back(u, e.to);
                }
            }
        }
    if (cut_edges.size() != 1) {
        cout << 0 << '\n';
        return 0;
    }
    auto edge = cut_edges[0];
    for (int i = 0; i < m; i++) {
        if ((edgesOrig[i].first == edge.first && edgesOrig[i].second == edge.second) || (edgesOrig[i].first == edge.second && edgesOrig[i].second == edge.first)) {
            cout << i + 1 << '\n';
            break;
        }
    }
}

Test details

Test 1

Verdict:

input
2 1
1 2
view save

correct output
1
view save

user output
(empty)

Test 2

Verdict:

input
3 2
1 2
2 3
view save

correct output
1
view save

user output
(empty)

Test 3

Verdict:

input
3 2
2 3
1 2
view save

correct output
2
view save

user output
(empty)

Test 4

Verdict:

input
3 3
1 2
1 3
2 3
view save

correct output
0
view save

user output
(empty)

Test 5

Verdict:

input
4 6
1 3
1 4
2 4
2 3
...
view save

correct output
0
view save

user output
(empty)

Test 6

Verdict:

input
4 4
1 3
2 3
3 4
1 2
view save

correct output
3
view save

user output
(empty)

Test 7

Verdict:

input
4 3
1 3
2 4
2 3
view save

correct output
1
view save

user output
(empty)

Test 8

Verdict:

input
4 3
2 3
2 4
1 3
view save

correct output
3
view save

user output
(empty)

Test 9

Verdict:

input
4 4
3 4
2 3
1 3
1 2
view save

correct output
1
view save

user output
(empty)

Test 10

Verdict:

input
5 7
2 5
3 5
3 4
1 5
...
view save

correct output
0
view save

user output
(empty)

Test 11

Verdict:

input
5 10
3 4
1 5
1 4
1 2
...
view save

correct output
0
view save

user output
(empty)

Test 12

Verdict:

input
5 6
1 4
3 4
4 5
2 3
...
view save

correct output
3
view save

user output
(empty)

Test 13

Verdict:

input
5 5
3 5
1 4
1 5
2 3
...
view save

correct output
0
view save

user output
(empty)

Test 14

Verdict:

input
5 7
2 4
1 5
3 5
2 5
...
view save

correct output
0
view save

user output
(empty)

Test 15

Verdict:

input
5 4
1 3
2 3
2 4
4 5
view save

correct output
1
view save

user output
(empty)

Test 16

Verdict:

input
5 4
2 4
3 5
2 3
1 4
view save

correct output
4
view save

user output
(empty)

Test 17

Verdict:

input
5 9
4 5
1 2
3 4
1 5
...
view save

correct output
0
view save

user output
(empty)

Test 18

Verdict:

input
5 10
1 3
2 5
4 5
3 4
...
view save

correct output
0
view save

user output
(empty)

Test 19

Verdict:

input
5 7
1 3
1 2
4 5
2 4
...
view save

correct output
0
view save

user output
(empty)

Test 20

Verdict:

input
10 12
2 5
4 9
4 7
3 9
...
view save

correct output
9
view save

user output
(empty)

Test 21

Verdict:

input
10 43
7 10
1 2
1 3
2 3
...
view save

correct output
0
view save

user output
(empty)

Test 22

Verdict:

input
10 11
2 5
2 3
6 7
1 2
...
view save

correct output
4
view save

user output
(empty)

Test 23

Verdict:

input
10 10
4 9
5 9
7 8
6 8
...
view save

correct output
8
view save

user output
(empty)

Test 24

Verdict:

input
10 12
7 9
3 8
3 5
4 5
...
view save

correct output
0
view save

user output
(empty)

Test 25

Verdict:

input
10 9
2 4
8 10
6 7
2 3
...
view save

correct output
9
view save

user output
(empty)

Test 26

Verdict:

input
10 9
3 5
5 7
1 6
4 6
...
view save

correct output
3
view save

user output
(empty)

Test 27

Verdict:

input
10 37
5 9
3 4
1 4
7 10
...
view save

correct output
0
view save

user output
(empty)

Test 28

Verdict:

input
10 44
2 6
1 2
1 6
4 7
...
view save

correct output
0
view save

user output
(empty)

Test 29

Verdict:

input
10 27
1 10
7 10
4 7
2 9
...
view save

correct output
0
view save

user output
(empty)

Test 30

Verdict:

input
100 107
44 59
24 76
35 79
14 57
...
view save

correct output
107
view save

user output
(empty)

Test 31

Verdict:

input
100 107
27 79
43 89
83 96
34 75
...
view save

correct output
42
view save

user output
(empty)

Test 32

Verdict:

input
100 143
13 14
20 59
25 95
38 84
...
view save

correct output
129
view save

user output
(empty)

Test 33

Verdict:

input
100 155
29 92
3 63
16 18
9 28
...
view save

correct output
36
view save

user output
(empty)

Test 34

Verdict:

input
100 105
74 85
6 49
7 81
45 55
...
view save

correct output
50
view save

user output
(empty)

Test 35

Verdict:

input
100 121
8 74
14 50
44 55
12 93
...
view save

correct output
0
view save

user output
(empty)

Test 36

Verdict:

input
100 102
54 97
45 82
30 78
40 44
...
view save

correct output
35
view save

user output
(empty)

Test 37

Verdict:

input
100 106
57 85
3 58
14 93
31 61
...
view save

correct output
8
view save

user output
(empty)

Test 38

Verdict:

input
100 188
3 58
53 63
8 19
97 100
...
view save

correct output
0
view save

user output
(empty)

Test 39

Verdict:

input
100 100
16 94
48 96
4 37
71 85
...
view save

correct output
41
view save

user output
(empty)

Test 40

Verdict:

input
200 207
111 188
80 121
115 170
157 175
...
view save

correct output
199
view save

user output
(empty)

Test 41

Verdict:

input
200 207
99 117
139 143
151 174
136 184
...
view save

correct output
190
view save

user output
(empty)

Test 42

Verdict:

input
200 287
36 180
125 138
33 147
38 188
...
view save

correct output
77
view save

user output
(empty)

Test 43

Verdict:

input
200 310
162 195
21 199
95 180
29 127
...
view save

correct output
30
view save

user output
(empty)

Test 44

Verdict:

input
200 205
140 187
127 185
100 196
55 144
...
view save

correct output
150
view save

user output
(empty)

Test 45

Verdict:

input
200 243
8 85
73 137
52 72
51 157
...
view save

correct output
53
view save

user output
(empty)

Test 46

Verdict:

input
200 202
45 72
5 96
1 31
35 187
...
view save

correct output
3
view save

user output
(empty)

Test 47

Verdict:

input
200 214
81 116
113 164
154 199
17 153
...
view save

correct output
45
view save

user output
(empty)

Test 48

Verdict:

input
200 375
68 93
93 101
87 109
23 56
...
view save

correct output
0
view save

user output
(empty)

Test 49

Verdict:

input
200 201
64 124
145 164
103 127
126 186
...
view save

correct output
137
view save

user output
(empty)

Test 50

Verdict:

input
1000 1007
61 967
252 530
105 953
490 826
...
view save

correct output
914
view save

user output
(empty)

Test 51

Verdict:

input
1000 1007
489 976
53 720
478 732
104 111
...
view save

correct output
248
view save

user output
(empty)

Test 52

Verdict:

input
1000 1435
520 551
702 787
76 719
619 993
...
view save

correct output
1114
view save

user output
(empty)

Test 53

Verdict:

input
1000 1550
206 315
476 801
287 713
456 677
...
view save

correct output
1059
view save

user output
(empty)

Test 54

Verdict:

input
1000 1005
304 771
84 930
17 988
282 364
...
view save

correct output
714
view save

user output
(empty)

Test 55

Verdict:

input
1000 1221
254 729
301 692
201 239
530 550
...
view save

correct output
406
view save

user output
(empty)

Test 56

Verdict:

input
1000 1002
147 586
502 522
194 372
176 451
...
view save

correct output
117
view save

user output
(empty)

Test 57

Verdict:

input
1000 1075
470 600
129 251
654 850
567 661
...
view save

correct output
642
view save

user output
(empty)

Test 58

Verdict:

input
1000 1874
668 731
316 335
532 731
523 839
...
view save

correct output
0
view save

user output
(empty)

Test 59

Verdict:

input
1000 1009
674 739
96 435
360 670
130 773
...
view save

correct output
768
view save

user output
(empty)

Test 60

Verdict:

input
100000 100007
44087 69715
31775 43251
18923 35874
36912 75163
...
view save

correct output
923
view save

user output
(empty)

Test 61

Verdict:

input
100000 100007
19253 34700
66338 83144
22343 27898
4199 35494
...
view save

correct output
9842
view save

user output
(empty)

Test 62

Verdict:

input
100000 143600
14018 46297
31183 86763
34508 87502
54400 64922
...
view save

correct output
0
view save

user output
(empty)

Test 63

Verdict:

input
100000 155080
7038 29509
13361 87647
1940 92912
7785 12866
...
view save

correct output
0
view save

user output
(empty)

Test 64

Verdict:

input
100000 100005
33360 89287
42922 67061
77709 78585
48488 51346
...
view save

correct output
523
view save

user output
(empty)

Test 65

Verdict:

input
100000 122199
24155 82039
27201 64021
37961 66619
7615 11277
...
view save

correct output
61740
view save

user output
(empty)

Test 66

Verdict:

input
100000 100002
13135 96454
53655 77933
52027 71763
40622 57175
...
view save

correct output
60082
view save

user output
(empty)

Test 67

Verdict:

input
100000 107630
30498 57903
5372 70239
51740 59293
41709 92770
...
view save

correct output
102920
view save

user output
(empty)

Test 68

Verdict:

input
100000 187345
5859 71722
58010 74508
66929 91927
15925 53657
...
view save

correct output
129660
view save

user output
(empty)

Test 69

Verdict:

input
100000 101036
13541 29328
50426 75396
46089 77950
42830 56873
...
view save

correct output
80466
view save

user output
(empty)

Tasks

A 3SUMB Distinct RoutesC Snakeless pathD Road blockade

Submissions (Dereden)

2025-10-20 17:29:54 2025-10-20 17:29:39 2025-10-20 17:22:03 2025-10-20 17:19:54