?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
72952750 |
Practice: dante_part_2 |
131D - 11 | C++17 (GCC 7-32) | Memory limit exceeded on test 8 | 528 ms | 262144 KB | 2020-03-11 15:17:02 | 2020-03-11 15:17:03 |
#include <iostream> #include <vector> #include <algorithm> #include <math.h> #include <unordered_map> #include <unordered_set> #include <iomanip> #include <list> #include <queue> #include <stack> #include <map> #define mod 1000000007 #define MAX 1000000007 using namespace std; bool dfs(vector<vector<int>> arr, vector<int> st, vector<int> &cycle, vector<bool> &visi, int i, int par){ if(visi[i]){ cycle[i] = 1; for(int j = st.size()-1; j >= 0 && st[j] != i; j--){ cycle[st[j]] = 1; } return true; } st.push_back(i); visi[i] = true; for(int j = 0; j < arr.size(); j++){ if(arr[i][j] == 1 && j != par){ bool curr = dfs(arr, st, cycle, visi, j, i); if(curr) return true; } } return false; } void f(vector<vector<int>> arr, vector<bool> &visi, vector<int> &res, int i, int val){ if(visi[i]) return; visi[i] = true; res[i] = val; for(int j = 0; j < arr.size(); j++){ if(arr[i][j] == 1) f(arr, visi, res, j, val+1); } } int main(){ int n; cin >> n; vector<vector<int>> arr(n, vector<int>(n,0)); vector<int> cycle(n,0), st; vector<bool> visi(n,false); for(int i = 0; i < n; i++){ int u, v; cin >> u >> v; arr[u-1][v-1] = arr[v-1][u-1] = 1; } dfs(arr, st, cycle, visi, 0, -1); // for(int i: cycle) cout << i << " "; // cout << endl; for(int i = 0; i < n; i++) visi[i] = (cycle[i] == 1 ? true : false); vector<int> res(n,0); for(int i = 0; i < n; i++){ if(visi[i] && cycle[i] == 1){ visi[i] = false; f(arr, visi, res, i, 0); } } for(int i: res) cout << i << " "; cout << endl; }
?
?
?
?