Task: | Course Schedule |
Sender: | fabiank |
Submission time: | 2024-10-07 15:50:14 +0300 |
Language: | C++ (C++20) |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.00 s | details |
#2 | ACCEPTED | 0.00 s | details |
#3 | ACCEPTED | 0.00 s | details |
#4 | ACCEPTED | 0.00 s | details |
#5 | ACCEPTED | 0.00 s | details |
#6 | ACCEPTED | 0.09 s | details |
#7 | ACCEPTED | 0.09 s | details |
#8 | ACCEPTED | 0.09 s | details |
#9 | ACCEPTED | 0.09 s | details |
#10 | ACCEPTED | 0.07 s | details |
#11 | ACCEPTED | 0.07 s | details |
#12 | ACCEPTED | 0.00 s | details |
#13 | ACCEPTED | 0.00 s | details |
#14 | ACCEPTED | 0.06 s | details |
#15 | ACCEPTED | 0.05 s | details |
#16 | ACCEPTED | 0.00 s | details |
#17 | ACCEPTED | 0.06 s | details |
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 valusing 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 sfor (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 |