— Dark mode

Aalto Competitive Programming 2024 - wk7 - Mon

Distinct Routes

  • Start: 2024-10-21 16:20:00
  • End: 2024-10-21 17:50:00
CSES - Aalto Competitive Programming 2024 - wk7 - Mon - Results
Submission details
Task:Distinct Routes
Sender:Niilo
Submission time:2024-10-21 16:50:33 +0300
Language:C++ (C++17)
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3ACCEPTED0.01 sdetails
#4ACCEPTED0.01 sdetails
#5ACCEPTED0.00 sdetails
#60.00 sdetails
#70.01 sdetails
#80.00 sdetails
#9ACCEPTED0.00 sdetails
#10ACCEPTED0.00 sdetails
#110.00 sdetails
#12ACCEPTED0.00 sdetails
#13ACCEPTED0.00 sdetails
#140.00 sdetails
#150.01 sdetails

Code

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

const int N = 500;
int W[N][N], W2[N][N];
vector<int> V[N];
int n, m;
bool Z[N];

ll dfs(int i, ll c, ll w0) {
  if (i == n-1) {
    return w0;
  }
  if (Z[i]) return 0;
  Z[i] = 1;
  for (int j : V[i]) {
    ll w = W[i][j];
    if (w >= c) {
      ll v = dfs(j,c,min(w0,w));
      if (v) {
        W[i][j] -= v;
        W[j][i] += v;
        return v;
      }
    }
  }
  return 0;
}

int main() {
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    V[a-1].push_back(b-1);
    V[b-1].push_back(a-1);
    W[a-1][b-1] += 1;
    ++W2[a-1][b-1];
  }
  ll ans = 0;
  for (ll c = 1; c >= 1; c /= 2) {
    while (1) {
      memset(Z,0,n);
      ll w = dfs(0,c,1e18);
      if (w == 0) break;
      ans += w;
    }
  }
  cout << ans << '\n';
  for (int i = 0; i < ans; ++i) {
    vector<int> P;
    P.push_back(0);
    while (P.back() != n-1) {
      int j = P.back();
      for (int k : V[j]) {
        if (W2[j][k]) {
          P.push_back(k);
          --W2[j][k];
          break;
        }
      }
      assert(P.back() != j);
    }
    cout << P.size() << '\n';
    for (int j : P) {
      cout << j+1 << ' ';
    }
    cout << '\n';
  }
}

Test details

Test 1

Verdict: ACCEPTED

input
2 1
1 2
view save

correct output
1
2
1 2 
view save

user output
1
2
1 2 
view save

Test 2

Verdict: ACCEPTED

input
4 2
1 2
3 4
view save

correct output
0
view save

user output
0
view save

Test 3

Verdict: ACCEPTED

input
500 996
1 2
2 500
1 3
3 500
...
view save

correct output
498
3
1 2 500 
3
1 3 500 
...
view save

user output
498
3
1 2 500 
3
1 3 500 
...
Truncated

Test 4

Verdict: ACCEPTED

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

correct output
1
500
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
view save

user output
1
500
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
Truncated

Test 5

Verdict: ACCEPTED

input
2 1
2 1
view save

correct output
0
view save

user output
0
view save

Test 6

Verdict:

input
40 1000
25 22
15 24
7 33
16 32
...
view save

correct output
21
44
1 35 39 34 29 32 22 38 20 30 1...
view save

user output
(empty)

Error:
code: input/code.cpp:63: int main(): Assertion `P.back() != j' failed.

Test 7

Verdict:

input
75 1000
72 6
46 66
63 45
70 46
...
view save

correct output
12
30
1 29 24 9 18 63 45 31 66 72 6 ...
view save

user output
(empty)

Error:
code: input/code.cpp:63: int main(): Assertion `P.back() != j' failed.

Test 8

Verdict:

input
100 1000
75 97
7 62
88 25
36 44
...
view save

correct output
9
51
1 35 15 86 79 34 43 94 83 75 9...
view save

user output
(empty)

Error:
code: input/code.cpp:63: int main(): Assertion `P.back() != j' failed.

Test 9

Verdict: ACCEPTED

input
3 2
1 2
2 3
view save

correct output
1
3
1 2 3 
view save

user output
1
3
1 2 3 
view save

Test 10

Verdict: ACCEPTED

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

correct output
2
6
1 2 3 4 5 11 
7
1 6 7 8 9 10 11 
view save

user output
2
6
1 2 3 4 5 11 
7
1 6 7 8 9 10 11 
view save

Test 11

Verdict:

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

correct output
2
5
1 2 6 7 8 
5
1 4 5 3 8 
view save

user output
(empty)

Error:
code: input/code.cpp:63: int main(): Assertion `P.back() != j' failed.

Test 12

Verdict: ACCEPTED

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

correct output
1
8
1 2 3 4 5 6 7 8 
view save

user output
1
8
1 2 3 4 5 6 7 8 
view save

Test 13

Verdict: ACCEPTED

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

correct output
3
3
1 2 7 
4
1 3 5 7 
...
view save

user output
3
3
1 2 7 
4
1 3 4 7 
...
view save

Test 14

Verdict:

input
7 15
3 6
5 2
5 4
3 5
...
view save

correct output
2
5
1 2 3 6 7 
4
1 4 5 7 
view save

user output
(empty)

Error:
code: input/code.cpp:63: int main(): Assertion `P.back() != j' failed.

Test 15

Verdict:

input
500 986
244 252
224 22
81 484
273 432
...
view save

correct output
116
5
1 129 142 473 500 
5
1 63 158 171 500 
...
view save

user output
(empty)

Error:
code: input/code.cpp:63: int main(): Assertion `P.back() != j' failed.

Tasks

A 3SUMB Distinct RoutesC Snakeless pathD Road blockade

Submissions (Niilo)

2024-10-21 16:54:03 2024-10-21 16:50:33