Submission details
Task:Internet connection
Sender:Roskis
Submission time:2020-09-19 15:25:09 +0300
Language:C++ (C++11)
Status:READY
Result:
Test results
testverdicttime
#10.01 sdetails
#2ACCEPTED0.01 sdetails
#3ACCEPTED0.01 sdetails
#4ACCEPTED0.01 sdetails
#5ACCEPTED0.01 sdetails
#60.63 sdetails
#70.63 sdetails
#80.62 sdetails
#90.63 sdetails
#100.63 sdetails
#11ACCEPTED0.01 sdetails
#12ACCEPTED0.01 sdetails
#13ACCEPTED0.01 sdetails
#140.61 sdetails
#15ACCEPTED0.01 sdetails
#16ACCEPTED0.01 sdetails
#17ACCEPTED0.01 sdetails
#180.61 sdetails
#190.61 sdetails
#20ACCEPTED0.01 sdetails
#210.63 sdetails
#220.62 sdetails

Compiler report

input/code.cpp: In function 'void DFS(int, int)':
input/code.cpp:66:7: warning: unused variable 'a' [-Wunused-variable]
   int a = 10;
       ^

Code

#include <bits/stdc++.h>
using namespace std;
#define N 1000

vector<int> g[N]; // g[i] represents all neighbors for node i

/*
//vector<int> g[N]; // g[i] represents all neighbors for node i
void bfs(int s) {
  // print bfstraversal starting at node s
  queue<int> q;
  vector<bool> vis(N);
  q.push(s);
  while(not q.empty()) {
    auto u = q.front();
    q.pop();
    if(not vis[u]) {
      cout << u << " ";
      vis[u] = true;
      for(auto v : g[u]) {
        q.push(v);
      }
    }
  }
}
*/

void printG() {
  cout << "G:" << endl;
  for (auto i: g) {
    cout << " ";
    for (auto j: i) {
      cout << j;
    }
  }
}

void remG(int a, int b) {
  //cout << "a:" << a << "b:" << b << endl;
  vector<int>::iterator pos = find(g[a].begin(), g[a].end(), b);
  if (pos != g[a].end())
      g[a].erase(pos);
}

bool DFSRec(int v, int f, bool visited[]) {
  //cout << v << " ";
  if (v == f) return true;

  visited[v] = true;

  list<int>::iterator i;
  for (auto i: g[v])
    if (!visited[i])
      if (DFSRec(i, f, visited)) {
        remG(v, i);
        return true;
      }
  return false;
}

void DFS(int s, int f) {
  bool *visited = new bool[N];
  for (int i = 0; i < N; i++)
    visited[i] = false;

  int a = 10;

  int paths = 0;

  while(DFSRec(s, f, visited)) {
    for (int i = 0; i < N; i++)
      visited[i] = false;
    paths++;
  }
  cout << paths;
}

int main() {
  int n, m;
  cin >> n >> m;
  for(int i=0; i<m; i++) {
    int v, w, x;
    cin >> v >> w >> x;
    for (int y=0; y<x; y++) {
      g[v].push_back(w);
      //g[w].push_back(v);
    }
  }

  //bfs(1);
  //printG();
  DFS(1, n);
  //printG();
}

Test details

Test 1

Verdict:

input
10 20
5 6 19
4 5 47
3 5 7
4 9 62
...

correct output
73

user output
69

Test 2

Verdict: ACCEPTED

input
10 20
2 4 63
7 9 54
6 7 16
2 3 9
...

correct output
110

user output
110

Test 3

Verdict: ACCEPTED

input
10 20
5 6 90
2 3 46
7 8 80
6 7 60
...

correct output
29

user output
29

Test 4

Verdict: ACCEPTED

input
10 20
3 4 76
5 7 8
3 8 71
4 7 24
...

correct output
95

user output
95

Test 5

Verdict: ACCEPTED

input
10 20
1 8 22
6 7 40
4 5 20
8 10 77
...

correct output
156

user output
156

Test 6

Verdict:

input
100 1000
63 85 864540192
22 91 974117435
64 66 953124912
85 88 6080960
...

correct output
4397669179

user output
(empty)

Test 7

Verdict:

input
100 1000
36 93 760720873
12 75 175717522
78 79 340128710
80 83 181753465
...

correct output
5298558023

user output
(empty)

Test 8

Verdict:

input
100 1000
20 60 909693891
55 91 570199535
21 41 118646902
37 82 824735480
...

correct output
5466229311

user output
(empty)

Test 9

Verdict:

input
100 1000
26 44 753330451
62 67 821574279
70 95 219303983
7 44 980013084
...

correct output
4893925638

user output
(empty)

Test 10

Verdict:

input
100 1000
15 89 501388091
50 71 396801720
15 92 324349822
29 85 184420157
...

correct output
6956499595

user output
(empty)

Test 11

Verdict: ACCEPTED

input
2 1
1 2 1

correct output
1

user output
1

Test 12

Verdict: ACCEPTED

input
2 1
2 1 1

correct output
0

user output
0

Test 13

Verdict: ACCEPTED

input
2 2
1 2 1
2 1 1

correct output
1

user output
1

Test 14

Verdict:

input
100 1000
1 2 539540023
2 3 244306651
3 4 253259012
3 5 630461598
...

correct output
0

user output
(empty)

Test 15

Verdict: ACCEPTED

input
4 5
1 2 2
1 3 5
2 4 3
3 2 2
...

correct output
4

user output
4

Test 16

Verdict: ACCEPTED

input
2 0

correct output
0

user output
0

Test 17

Verdict: ACCEPTED

input
100 0

correct output
0

user output
0

Test 18

Verdict:

input
100 196
1 2 1000000000
2 100 1000000000
1 3 1000000000
3 100 1000000000
...

correct output
98000000000

user output
(empty)

Test 19

Verdict:

input
100 99
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
...

correct output
1000000000

user output
(empty)

Test 20

Verdict: ACCEPTED

input
2 2
2 1 1
1 2 1

correct output
1

user output
1

Test 21

Verdict:

input
4 6
1 2 1000000000
1 3 1000000000
2 3 1
2 4 1000000000
...

correct output
2000000000

user output
(empty)

Test 22

Verdict:

input
4 6
1 2 1000000000
1 3 1000000000
2 4 1000000000
2 3 1
...

correct output
2000000000

user output
(empty)