Advertisement
Korotkodul

oi-2 dfs Производство деталей ЩЛ

Jan 17th, 2022 (edited)
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.25 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4. #include <queue>
  5. #include <algorithm>
  6. #include <string>
  7. #include <stack>
  8. #include <set>
  9. #include <map>
  10. #define pii pair <int,int>
  11. #define vec vector
  12. using namespace std;
  13. using ll = long long;
  14. using ld = long double;
  15. using db = double;
  16. void cv(vector <int> &v){
  17. for (auto x: v) cout<<x<<' ';
  18. cout<<"\n";
  19. }
  20.  
  21. void cvl(vector <ll> &v){
  22. for (auto x: v) cout<<x<<' ';
  23. cout<<"\n";
  24. }
  25.  
  26.  
  27. void cvv(vector <vector <int> > &v){
  28. for (auto x: v) cv(x);
  29. cout<<"\n";
  30. }
  31.  
  32. const int wh=0, gr=1, bl=2;
  33. vector <int> tm;//time per det
  34. ll tot=0; // tot time
  35. vector <vector<int> > G;
  36. vector <int> ans;
  37. vector <int> clr;
  38.  
  39. void dfs(int v){
  40. tot += tm[v];
  41. clr[v] = gr;
  42. for (int u: G[v]){
  43. if (clr[u] == wh) dfs(u);
  44. }
  45. ans.push_back(v+1);
  46. clr[v] = bl;
  47. }
  48.  
  49. int main()
  50. {
  51. ios::sync_with_stdio(0);
  52. cin.tie(0);
  53. cout.tie(0);
  54. int n,k;
  55. cin>>n;
  56. G.resize(n);
  57. tm.resize(n);
  58. clr.assign(n, wh);
  59. for (int &x: tm) cin>>x;
  60. for (int i = 0; i < n;++i){
  61. cin>>k;
  62. for (int j=0;j<k;++j){
  63. int d; cin>>d; d--;
  64. G[i].push_back(d);
  65. }
  66. }
  67. dfs(0);
  68. cout<<tot<<' '<<ans.size()<<' '<<"\n";
  69. cv(ans);
  70. }
  71.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement