fork(2) download
copy 
  1. #include <vector>
  2. #include <cstdio>
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <stack>
  6. #include <bitset>
  7. using namespace std;
  8. const int NMAX  = 100004;
  9. const int VALMAX = 2e6;
  10. vector < int > Tree[NMAX];
  11. int value[NMAX], niv[NMAX] , answer[NMAX];
  12. bitset < VALMAX+6> viz;
  13. int prime[2*NMAX],pos[6+VALMAX];
  14. stack < int > St[2*NMAX]; 
  15. inline void Eratosthenes(){
  16.     prime[++prime[0]] = 2; 
  17.     pos[2] = 1;
  18.     for(int i = 3;i <= VALMAX;i += 2)
  19.         if(!viz[i]){
  20.             prime[++prime[0]] = i;
  21.             pos[i] = prime[0];
  22.             for(long long j = 1LL*i*i;j <= VALMAX; j += 2*i)
  23.                 viz[j] = 1;
  24.         }
  25. }
  26. inline void DFS(const int node,const int father){
  27.     vector < int > v;
  28.     int d = 2,step = 1;
  29.     int x = value[node];
  30.     answer[node] = 0;
  31.     while(d*d <= x){
  32.         if(x%d==0){
  33.             if(!St[pos[d]].empty()){
  34.                 int y = St[pos[d]].top();
  35.                 if(niv[y] > niv[answer[node]])
  36.                     answer[node] = y;
  37.             }
  38.             v.push_back(pos[d]);
  39.             St[pos[d]].push(node);
  40.             while(x%d==0)
  41.                 x /= d;
  42.         }
  43.         ++step;
  44.         d = prime[step];
  45.     }
  46.     if(x > 1){
  47.         if(!St[pos[x]].empty()){
  48.             int y = St[pos[x]].top();
  49.             if(niv[y] > niv[answer[node]])
  50.                  answer[node] = y;
  51.         }
  52.         v.push_back(pos[x]);
  53.         St[pos[x]].push(node);
  54.     }
  55.     for(vector < int > ::iterator it = Tree[node].begin(); it != Tree[node].end(); ++it)
  56.         if(*it!=father){
  57.             niv[*it] = niv[node] + 1;
  58.             DFS(*it,node);
  59.         }
  60.     for(vector < int > ::iterator it = v.begin(); it != v.end() ; ++it)
  61.         St[*it].pop();
  62.     v.clear();
  63. }
  64.  
  65. int main(){
  66.     #ifndef ONLINE_JUDGE
  67.         freopen("date.in","r",stdin);
  68.         freopen("date.ok","w",stdout);
  69.     #endif
  70.     cin.sync_with_stdio(false);
  71.     Eratosthenes();
  72.     int n, m;
  73.     cin >> n >> m;
  74.     for(int i = 1;i <= n; ++i)
  75.         cin >> value[i];
  76.     for(int i = 1;i < n; ++i){
  77.         int x, y;
  78.         cin >> x >> y;
  79.         Tree[x].push_back(y);
  80.         Tree[y].push_back(x);
  81.     }
  82.     niv[1] = 1;
  83.     DFS(1,-1);
  84.     while(m--){
  85.         int operation, x, y;
  86.         cin >> operation >> x;
  87.         if(operation == 1){
  88.             if(answer[x] > 0)
  89.                 cout<<answer[x]<<"\n";
  90.             else
  91.                 cout<<"-1\n";
  92.         }
  93.         else{
  94.             cin >> y;
  95.             value[x] = y;
  96.             DFS(1,-1);
  97.         }
  98.     }
  99.     return 0;
  100. }
Runtime error #stdin #stdout 0.17s 131904KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/AlivM9
language:
C++14 (gcc 8.3)
created:
10 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!