Advertisement
Guest User

Untitled

a guest
Dec 29th, 2019
478
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.07 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <set>
  5. #include <queue>
  6. #include <algorithm>
  7. #include <string>
  8. #include <cmath>
  9. #include <cstdio>
  10. #include <iomanip>
  11. #include <fstream>
  12. #include <cassert>
  13. #include <cstring>
  14. #include <unordered_set>
  15. #include <unordered_map>
  16. #include <numeric>
  17. #include <ctime>
  18. #include <bitset>
  19. #include <random>
  20. #include <complex>
  21. #include <random>
  22. #include <functional>
  23.  
  24. using namespace std;
  25.  
  26. void solve() {
  27.     int n;
  28.     cin >> n;
  29.     vector<int> a(n + 1);
  30.     vector<vector<int>> g(n + 1);
  31.     for (int i = 1; i <= n; i++) {
  32.         cin >> a[i];
  33.         g[i].push_back(i - a[i]);    
  34.     }
  35.     for (int i = 1; i <= n; i++) {
  36.         if (a[i] == 0) {
  37.             cout << 1 << '\n' << i << '\n';
  38.             return;
  39.         }
  40.     }
  41.     vector<int> used(n + 1);
  42.     pair<int, int> rs = {-1, -1};
  43.     function<void(int)> dfs = [&](int cur) {
  44.         used[cur] = 1;
  45.         for (auto t : g[cur]) {
  46.             if (used[t] == 0) {
  47.                 dfs(t);
  48.             }
  49.             if (used[t] == 1) {
  50.                 rs = {cur, t};
  51.             }
  52.         }
  53.         used[cur] = 2;
  54.     };
  55.     for (int i = 1; i <= n; i++) {
  56.         if (used[i] == 0) {
  57.             dfs(i);
  58.         }
  59.     }
  60.     swap(rs.first, rs.second);
  61.     fill(used.begin(), used.end(), 0);
  62.     vector<int> p(n + 1);
  63.     function<void(int, int)> dfs2 = [&](int cur, int pr) {
  64.         used[cur] = 1;
  65.         p[cur] = pr;
  66.         for (auto t : g[cur]) {
  67.             if (used[t] == 0) {
  68.                 dfs2(t, cur);
  69.             }
  70.         }
  71.         used[cur] = 2;
  72.     };
  73.     dfs2(rs.first, -1);
  74.     assert(used[rs.second]);
  75.     vector<int> v = {rs.first};
  76.     int cur = rs.second;
  77.     while (cur != rs.first) {
  78.         v.push_back(cur);
  79.         cur = p[cur];
  80.     }
  81.     cout << v.size() << '\n';
  82.     for (auto t : v) {
  83.         cout << t << ' ';
  84.     }
  85.     cout << '\n';
  86.  
  87. }
  88.  
  89. signed main() {
  90.     ios_base::sync_with_stdio(false);
  91.     cin.tie(0);
  92.  
  93.     int q;
  94.     cin >> q;
  95.     while (q--) {
  96.         solve();
  97.     }
  98. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement