fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define MAX 100005
  4. #define endl '\n'
  5.  
  6. using namespace std;
  7.  
  8. typedef long long ll;
  9. typedef double lf;
  10. typedef vector<ll> vi;
  11.  
  12. ll next_table[MAX], group[MAX], pos_in_group[MAX], tag_table[MAX], table_tag[MAX];
  13. vi cycles[MAX];
  14.  
  15. int main() {
  16.     ios_base::sync_with_stdio(false);
  17.     cin.tie(0);
  18.  
  19.     int n, k;
  20.     cin >> n >> k;
  21.  
  22.     for (ll i = 0; i < n; ++i) {
  23.         ll x;
  24.         cin >> x;
  25.         cin >> next_table[--x];
  26.         next_table[x]--;
  27.         tag_table[i] = x;
  28.         table_tag[x] = i;
  29.     }
  30.     vector<bool> analizados(n);
  31.     int grupo = 0;
  32.     for (ll j = 0; j < n; ++j) {
  33.         if (analizados[j])
  34.             continue;
  35.         ll pos = j, p = 0;
  36.         while (!analizados[pos]) {
  37.             group[pos] = grupo;
  38.             pos_in_group[pos] = p++;
  39.             cycles[grupo].push_back(pos);
  40.             analizados[pos] = true;
  41.             pos = next_table[pos];
  42.         }
  43.         grupo++;
  44.     }
  45.  
  46.     ll p, time;
  47.     for (ll i = 0; i < k; ++i) {
  48.         cin >> p >> time;
  49.  
  50.         ll len = cycles[group[table_tag[--p]]].size();
  51.         ll q = pos_in_group[table_tag[p]];
  52.         cout << tag_table[cycles[group[table_tag[p]]][(time + q) % len]] + 1 << endl;
  53.     }
  54. }
Runtime error #stdin #stdout 0s 8544KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/wSyJmn
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!