— 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:snude
Submission time:2024-10-21 17:16:16 +0300
Language:C++ (C++11)
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3ACCEPTED0.01 sdetails
#4ACCEPTED0.00 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.00 sdetails
#7ACCEPTED0.00 sdetails
#8ACCEPTED0.00 sdetails
#9ACCEPTED0.00 sdetails
#10ACCEPTED0.00 sdetails
#110.00 sdetails
#12ACCEPTED0.00 sdetails
#13ACCEPTED0.00 sdetails
#14ACCEPTED0.00 sdetails
#150.00 sdetails

Code

#include <algorithm>
#include <climits>
#include <cmath>
#include <iostream>
#include <queue>
#include <vector>

// Debug printing
#ifdef DEBUG
#define deb(fmt, args...) printf("DEBUG: %d: " fmt, __LINE__, ##args)
#else
#define deb(fmt, args...)
#endif

using namespace std;
using ll = long long;

void print_array(vector<int> in, const string title = "Vector")
{
	cout << title << " [\n";
	for (const auto &el : in) {
		cout << el << " ";
	}
	cout << "\n] END\n";
}

void print_matrix(vector<vector<int> > in, const string title = "Matrix")
{
	cout << title << " [\n";
	for (unsigned int i = 0; i < in.size(); i++) {
		cout << "row " << i << ": ";
		for (unsigned int j = 0; j < in[i].size(); j++) {
			cout << in[i][j] << " ";
		}
		cout << "\n";
	}
	cout << "] END\n";
}

int target;
int found = true;
vector<int> path;
bool visited[500];

void dijkstra(vector<vector<int> > &adj, vector<vector<int> > &edges, int n,
	      vector<int> &path)
{
	priority_queue<pair<ll, ll> > q;
	vector<int> distance(n + 1, INT_MAX);
	vector<int> predecessor(n + 1, 0);
	vector<bool> processed(n + 1, false);

	distance[1] = 0;
	q.push({ 0, 1 });
	while (!q.empty()) {
		ll a = q.top().second;
		q.pop();
		if (processed[a])
			continue;
		processed[a] = true;
		for (auto u : adj[a]) {
			vector<int> edge = edges[u];
            if (edge[2] < 1) continue;
			ll b = edge[1], w = 1;
			if (distance[a] + w < distance[b]) {
				distance[b] = distance[a] + w;
				predecessor[b] = u;
				q.push({ -distance[b], b });
			}
		}
	}

	// find shortest path
    if (predecessor[n] == 0) {
        found = false;
        return;
    }
    found = true;
    int v = n;
	int e = predecessor[v];
    int index = 0;
	while (v != 1) {
		e = predecessor[v];
		path.push_back(e);
		v = edges[e][0];
        index++;
	}
    reverse(path.begin(), path.end());
}

void find_min_cut(vector<vector<int> > &adj, vector<vector<int> > &edges)
{

}

// void dfs(int s, bool visited[], vector<vector<int>> &adj, vector<vector<int>> &edges)
// {
// 	if (visited[s]) {
// 		return;
// 	};
// 	visited[s] = true;

// 	// Do something with this node

// 	for (auto u : adj[s]) {
//         vector<int> e = edges[u];
// 		dfs(e[1], visited, adj, edges);
// 	}
// }

void dfs(int s, vector<vector<int> > &adj, vector<vector<int> > &edges,
	 vector<int> &path)
{
	if (found) {
		return;
	}
	if (visited[s]) {
		return;
	};
	visited[s] = true;
	if (s == target) {
		found = true;
		return;
	}
 
	for (auto u : adj[s]) {
        // ll a = edges[u][0];
        ll b = edges[u][1];
        ll c = edges[u][2];
        // deb("s: %d, a: %d, b: %d, c: %d\n", s, a, b, c);
        if (c > 0) {
            path.push_back(u);
            dfs(b, adj, edges, path);
            if (found) return;
            path.pop_back();
        }
	}
}

int main(int argc, char *argv[])
{
	int n, m;
	cin >> n >> m;
	target = n;

	// each edge is of form (a, b, c)
	vector<vector<int> > edges(m + 1, vector<int>(3));
	for (int i = 1; i < m + 1; i++) {
		cin >> edges[i][0] >> edges[i][1];
        edges[i][2] = 1;
	}

	// adjacent structure contains the edge indices that are adjacent to the
	// node
	vector<vector<int> > adj(n + 1, vector<int>());
	for (int j = 1; j < m + 1; j++) {
		adj[edges[j][0]].push_back(j);
	}

    vector<vector<int>> paths;
    while (found) {
        found = false;
		for (int i = 0; i < n + 1; i++)
			visited[i] = false;

		path.clear();
        dfs(1, adj, edges, path);
        if (found) {
            paths.push_back(path);
        }
        for (auto e : path) {
            edges[e][2] -= 1;
        }
    }

    cout << paths.size() << "\n";
    for (auto path : paths) {
        cout << path.size() + 1 << "\n";
        for (auto e : path) {
            cout << edges[e][0] << " ";
            edges[e][2] -= 1;
        }
        cout << n << "\n";
    }

    // ll speed = 0;
    // while (found) {
    // 	found = false;
    // 	for (int i = 0; i < n + 1; i++)
    // 		visited[i] = false;

    // 	path.clear();
    //        dijkstra(adj, edges, n, path);
    // 	if (found) {
    // 		int residual = INT_MAX;

    // 		// find residual capacity of the path
    // 		for (auto e : path) {
    // 			vector<int> edge = edges[e];
    // 			if (edge[2] < residual)
    // 				residual = edge[2];
    // 		}
    // 		// speed += residual;

    // 		// update flows
    // 		for (auto e : path) {
    // 			edges[e][2] -= residual;
    // 		}
    // 	}
    // }

    // bool visited[n + 1];
    // for (int i = 0; i < n + 1; i++)
    // 	visited[i] = false;

    // dfs(1, visited, adj, edges);
    // for (int i = 0; i < n; i++) {
    //     if (visited[i]) {
    //         for (auto e : adj[i]) {
    //             vector<int> edge = edges[e];
    //             int a = edges[e][0];
    //             int b = edges[e][1];
    //             if (!visited[b]) {

    //             }
    //         }
    //     }
    // }
    // find_min_cut();

    // cout << speed << "\n";

    return 0;
}

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: ACCEPTED

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
21
15
1 35 39 34 24 2 18 25 22 38 28...
Truncated

Test 7

Verdict: ACCEPTED

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
12
61
1 29 24 9 18 36 26 19 20 50 62...
Truncated

Test 8

Verdict: ACCEPTED

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
9
87
1 35 15 86 79 67 13 41 52 6 58...
Truncated

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
1
4
1 2 3 8
view save

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: ACCEPTED

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
2
5
1 2 3 6 7
4
1 4 5 7
view save

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
86
5
1 129 142 473 500
5
1 63 158 171 500
...
Truncated

Tasks

A 3SUMB Distinct RoutesC Snakeless pathD Road blockade

Submissions (snude)

2024-10-21 17:38:34 2024-10-21 17:38:06 2024-10-21 17:16:16