CSES - Aalto Competitive Programming 2024 - wk6 - Homework - Results
Submission details
Task:Course Schedule
Sender:fabiank
Submission time:2024-10-07 15:50:14 +0300
Language:C++ (C++20)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3ACCEPTED0.00 sdetails
#4ACCEPTED0.00 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.09 sdetails
#7ACCEPTED0.09 sdetails
#8ACCEPTED0.09 sdetails
#9ACCEPTED0.09 sdetails
#10ACCEPTED0.07 sdetails
#11ACCEPTED0.07 sdetails
#12ACCEPTED0.00 sdetails
#13ACCEPTED0.00 sdetails
#14ACCEPTED0.06 sdetails
#15ACCEPTED0.05 sdetails
#16ACCEPTED0.00 sdetails
#17ACCEPTED0.06 sdetails

Code

#include <bits/stdc++.h>
#define REP(i, a, b) for (int i = a; i < b; i++)
// Type Aliases for 1D and 2D vectors with initialization
#define vll(n, val) vector<long long>(n, val) // 1D vector of long longs with size n, initialized to val
#define ll long long
#define vvi(n, m, val) vector<vector<int>>(n, vector<int>(m, val)) // 2D vector of ints (n x m), initialized to val
#define vvll(n, m, val) vector<vector<long long>>(n, vector<long long>(m, val)) // 2D vector of long longs (n x m), initialized to val
using namespace std;
void print_vector(vector<int> &x)
{
for (int v : x)
{
cout << v << " ";
}
cout << "\n";
}
void print_matrix(vector<vector<int>> &matrix)
{
cout << "\n"
<< "----------------" << "\n";
for (vector<int> row : matrix)
{
print_vector(row);
}
cout << "\n"
<< "----------------" << "\n";
}
int calc_max_digit(int n)
{
int max_digit = 0;
while (n > 0 && max_digit < 9)
{
int digit = n % 10;
if (digit > max_digit)
{
max_digit = digit;
}
n /= 10;
}
return max_digit;
}
// edges as edge list for outgoing node as pairs (end, cost)
vector<ll> dijkstras(int start_point, vector<vector<pair<int, int>>> edges)
{
int n = edges.size();
vector<bool> processed(n, false);
vector<ll> distances(n, LLONG_MAX);
distances[start_point] = 0;
priority_queue<pair<ll, int>> pq;
pq.push({0, start_point});
while (!pq.empty())
{
int curr = pq.top().second;
pq.pop();
if (processed[curr])
{
continue;
}
processed[curr] = true;
ll distance = distances[curr];
for (pair<int, int> edge : edges[curr])
{
if (distance + edge.second < distances[edge.first])
{
distances[edge.first] = distance + edge.second;
pq.push({-distances[edge.first], edge.first});
}
}
}
return distances;
}
bool topological_sort_dfs(int s, vector<vector<int>> &adj, vector<short> &status, vector<int> &result)
{
if (status[s] == 1)
{
return false;
}
else if (status[s] == 2)
{
return true;
}
status[s] = 1;
// process node s
for (auto u : adj[s])
{
bool acylic = topological_sort_dfs(u, adj, status, result);
if (!acylic)
{
return false;
}
}
status[s] = 2;
result.push_back(s);
// cout << "Finished " << s << "\n";
return true;
}
bool topological_sort(vector<vector<int>> &adj, vector<int> &result, int start = 0)
{
int n = adj.size();
vector<short> status(n, 0);
for (int i = start; i < n; i++)
{
if (status[i] == 0)
{
bool acyclic = topological_sort_dfs(i, adj, status, result);
if (!acyclic)
{
return false;
}
}
}
return true;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> adj(n + 1, vector<int>());
for (int i = 0; i < m; i++)
{
int start, end;
cin >> start >> end;
adj[start].push_back(end);
}
vector<int> result;
bool acylic = topological_sort(adj, result, 1);
if (!acylic)
{
cout << "IMPOSSIBLE";
}
else
{
for (vector<int>::reverse_iterator riter = result.rbegin();
riter != result.rend(); ++riter)
{
cout << *riter << " ";
}
// for (int o : result)
// {
// cout << o << " ";
// }
}
cout << endl;
}

Test details

Test 1

Verdict: ACCEPTED

input
10 20
5 2
2 4
8 9
6 4
...

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

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

Test 2

Verdict: ACCEPTED

input
10 20
2 7
1 10
9 5
9 7
...

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

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

Test 3

Verdict: ACCEPTED

input
10 20
8 5
2 3
10 1
9 1
...

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

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

Test 4

Verdict: ACCEPTED

input
10 20
5 10
10 3
9 10
6 2
...

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

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

Test 5

Verdict: ACCEPTED

input
10 20
2 9
4 8
9 1
10 6
...

correct output
IMPOSSIBLE

user output
IMPOSSIBLE

Test 6

Verdict: ACCEPTED

input
100000 200000
78359 8853
18190 30703
11401 30087
34627 11535
...

correct output
2 3 8 9 16 18 21 22 27 34 36 4...

user output
99998 99996 99994 99993 99992 ...
Truncated

Test 7

Verdict: ACCEPTED

input
100000 200000
32395 2098
67067 31866
31867 67167
78488 33397
...

correct output
9 11 13 16 22 35 37 38 40 44 5...

user output
100000 99994 99991 99986 99983...
Truncated

Test 8

Verdict: ACCEPTED

input
100000 200000
19035 36947
13730 46121
99449 77790
15626 11731
...

correct output
1 7 15 17 18 34 38 41 48 49 51...

user output
100000 99998 99996 99993 99992...
Truncated

Test 9

Verdict: ACCEPTED

input
100000 200000
14188 9709
46541 20871
32203 88809
99879 54779
...

correct output
6 10 11 16 17 19 21 22 23 28 3...

user output
99996 99992 99991 99986 99985 ...
Truncated

Test 10

Verdict: ACCEPTED

input
100000 200000
41882 61162
28138 18053
74649 74863
69760 74508
...

correct output
IMPOSSIBLE

user output
IMPOSSIBLE

Test 11

Verdict: ACCEPTED

input
100000 199998
1 100000
1 100000
2 100000
2 100000
...

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

user output
99999 99998 99997 99996 99995 ...
Truncated

Test 12

Verdict: ACCEPTED

input
2 2
1 2
2 1

correct output
IMPOSSIBLE

user output
IMPOSSIBLE

Test 13

Verdict: ACCEPTED

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

correct output
IMPOSSIBLE

user output
IMPOSSIBLE

Test 14

Verdict: ACCEPTED

input
99999 149997
1 3
3 5
5 7
7 9
...

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

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

Test 15

Verdict: ACCEPTED

input
100000 149998
2 1
3 2
4 3
5 4
...

correct output
100000 99999 99998 99997 99996...

user output
100000 99999 99998 99997 99996...
Truncated

Test 16

Verdict: ACCEPTED

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

correct output
IMPOSSIBLE

user output
IMPOSSIBLE

Test 17

Verdict: ACCEPTED

input
100000 200000
1 1
1 1
2 2
2 2
...

correct output
IMPOSSIBLE

user output
IMPOSSIBLE