fork download 
  1.     #include <bits/stdc++.h>
  2.     #include <chrono>
  3.     using namespace std;
  4.     using namespace chrono;
  5.     // "AJEET JAIN"----"JAI JINENDRA"  
  6.     /* "णमो अरिहंताणं",
  7.         "णमो सिद्धाणं",
  8.         "णमो आयरियाणं",
  9.         "णमो उवज्झायाणं",
  10.         "णमो लोए सव्वसाहूणं",
  11.         "",
  12.         "एसो पंच नमोक्कारो, सव्व पावप्पणासणो",
  13.         "मंगलाणं च सव्वेसिं, पडमं हवै मंगलं",   */
  14.  
  15.  
  16.     // Aliases to op
  17.     using ll = long long;
  18.     using ull = unsigned long long;
  19.     using ld = double;
  20.     using vll = vector<ll>;
  21.  
  22.  
  23.     // Constants
  24.     constexpr ll INF = 4e18;
  25.     constexpr ld EPS = 1e-9;
  26.     constexpr ll MOD = 1e9 + 7;
  27.  
  28.  
  29.  
  30.     // Macros
  31.     #define F first
  32.     #define S second
  33.     #define all(x) begin(x), end(x)
  34.     #define allr(x) rbegin(x), rend(x)
  35.     #define py cout<<"YES\n";
  36.     #define pn cout<<"NO\n";
  37.     #define forn(i,n) for(int i=0;i<n;i++)
  38.     #define for1(i,n) for(int i=1;i<=n;i++)
  39.  
  40.     // #define insert push_back
  41.     #define pb push_back
  42.     #define MP make_pair
  43.     #define endl '\n'
  44.  
  45.     /*
  46.       remove substring or subarray ---> try to think about sliding w
  47.     
  48.     */                  
  49.  
  50.      /*
  51.       
  52.      Golden Rule
  53.  
  54.      1) problem is easy
  55.      2) proofs is easy
  56.      3) implementation is easy
  57.      
  58.      /*
  59.          ROUGH --
  60.                  
  61.      */
  62.  
  63. vector<int> dfs_ord , dfs_size;
  64.  
  65. void DFS(int node , vector<ll> G[] , vector<int> &used , vector<int> &parent){
  66.     used[node] = 1;
  67.     dfs_ord.push_back(node);
  68.     dfs_size[node] = 1;
  69.  
  70.     for(auto u : G[node]){
  71.         if(used[u] == 0){
  72.             parent[u] = node;
  73.             DFS(u , G , used , parent);
  74.             dfs_size[node] += dfs_size[u];
  75.         }
  76.     }
  77. }
  78.  
  79. void AJNJ(){
  80.     ll n , m;
  81.     cin >> n >> m;
  82.     vector<ll> G[n + 5];
  83.  
  84.     for(int i = 1 ; i <= m ; i++){
  85.         ll u , v;
  86.         cin >> u >> v;
  87.         G[u].push_back(v);
  88.         G[v].push_back(u);
  89.     }
  90.  
  91.     for(int i = 1 ; i <= n ; i++){
  92.         sort(G[i].begin() , G[i].end());
  93.     }
  94.  
  95.     vector<int> used(n + 5 , 0);
  96.     vector<int> parent(n + 5 , -1);
  97.     dfs_size.assign(n + 5 , 0);
  98.  
  99.     DFS(1 , G , used , parent);
  100.  
  101.     map<ll , ll> index_dfs_order;
  102.     for(int i = 0 ; i < dfs_ord.size() ; i++){
  103.         index_dfs_order[dfs_ord[i]] = i;
  104.     }
  105.  
  106.     int q;
  107.     cin >> q;
  108.     while(q--){
  109.         int node , indx;
  110.         cin >> node >> indx;
  111.  
  112.         ll l = index_dfs_order[node];
  113.  
  114.         if(indx > dfs_size[node]){
  115.             cout << "-1" << endl;
  116.         }
  117.         else{
  118.             cout << dfs_ord[l + indx - 1] << endl;
  119.         }
  120.     }
  121. }
  122.  
  123.     int main(){
  124.         ios::sync_with_stdio(0);
  125.         cin.tie(0);
  126.         cout.tie(0);
  127.         int T = 1;
  128.         cin>>T;
  129.         auto start1 = high_resolution_clock::now();
  130.         while(T--){
  131.             AJNJ();
  132.         }
  133.         auto stop1 = high_resolution_clock::now();
  134.         auto duration = duration_cast<microseconds>(stop1 - start1);
  135.         cerr << "Time: " << duration . count() / 1000 << " ms" << endl;
  136.  
  137.         return 0;
  138.     }
Success #stdin #stdout #stderr 0.04s 150860KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
Time: 37 ms
https://ideone.com/QxMNWp
language:
C++14 (clang 8.0)
created:
2 days 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!