shahil_005

MATOM_t_cpp

Feb 22nd, 2021
72
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. //----------------------------------- DEBUG -----------------------------------
  6. #define sim template < class c
  7. #define ris return * this
  8. #define dor > debug & operator <<
  9. #define eni(x) sim > typename \
  10. enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
  11. sim > struct rge { c b, e; };
  12. sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
  13. sim > auto dud(c* x) -> decltype(cerr << *x, 0);
  14. sim > char dud(...);
  15. struct debug {
  16. #ifdef LOCAL
  17. ~debug() { cerr << endl; }
  18. eni(!=) cerr << boolalpha << i; ris; }
  19. eni(==) ris << range(begin(i), end(i)); }
  20. sim, class b dor(pair < b, c > d) {
  21.   ris << "(" << d.first << ", " << d.second << ")";
  22. }
  23. sim dor(rge<c> d) {
  24.   *this << "[";
  25.   for (auto it = d.b; it != d.e; ++it)
  26.     *this << ", " + 2 * (it == d.b) << *it;
  27.   ris << "]";
  28. }
  29. #else
  30. sim dor(const c&) { ris; }
  31. #endif
  32. };
  33. #define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
  34. // debug & operator << (debug & dd, P p) { dd << "(" << p.x << ", " << p.y << ")"; return dd; }
  35.  
  36. //----------------------------------- END DEBUG --------------------------------
  37.  
  38. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  39.  
  40. #define trav(a,x) for (auto& a : x)
  41. #define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
  42.  
  43. //----------------------------------- DEFINES -----------------------------------
  44.  
  45. #define sz(x) (int)(x).size()
  46. #define mp make_pair
  47. #define eb emplace_back
  48. #define pb push_back
  49. #define lb lower_bound
  50. #define ub upper_bound
  51. #define all(x) x.begin(), x.end()
  52. #define rall(x) x.rbegin(), x.rend()
  53. #define ins insert
  54. #define nl '\n'
  55.  
  56. //----------------------------------- END DEFINES --------------------------------
  57.  
  58. //-------------------------- CUSTOM UNORDERED MAP HASH ---------------------------
  59.  
  60. struct custom_hash{
  61.     static uint64_t splitmix64(uint64_t x){
  62.         x += 0x9e3779b97f4a7c15;
  63.         x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
  64.         x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
  65.         return x ^ (x >> 31);
  66.     }
  67.     size_t operator()(uint64_t a) const {
  68.         static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
  69.         return splitmix64(a + FIXED_RANDOM);
  70.     }
  71.     template<class T> size_t operator()(T a) const {
  72.         static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
  73.         hash<T> x;
  74.         return splitmix64(x(a) + FIXED_RANDOM);
  75.     }
  76.     template<class T, class H> size_t operator()(pair<T, H> a) const {
  77.         static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
  78.         hash<T> x;
  79.         hash<H> y;
  80.         return splitmix64(x(a.first) * 37 + y(a.second) + FIXED_RANDOM);
  81.     }
  82. };
  83. template<class T, class H>using umap=unordered_map<T,H,custom_hash>;
  84.  
  85. //----------------------- CUSTOM UNORDERED MAP HASH END--------------------------
  86.  
  87. vector<int> primes;
  88.  
  89. void preprocess() {
  90.     vector<bool> seive(1000100, true);
  91.     seive[0] = seive[1] = false;
  92.     for(int i=2;i*i<1000100;i++) {
  93.         if(seive[i]) {
  94.             for(int j=i*i;j<1000100;j+=i) {
  95.                 seive[j] = false;
  96.             }
  97.         }
  98.     }
  99.     for(int i=2;i<1000100;i++) {
  100.         if(seive[i]) primes.push_back(i);
  101.     }
  102. }
  103.  
  104. vector<vector<int>> adj;
  105. vector<int> final_score, initial_score, transition_score, final_node;
  106.  
  107. void dfs(int node, int par) {
  108.     int min_score = final_score[node];
  109.     int curr_node = node;
  110.  
  111.     for(int child: adj[node]) {
  112.         if(child != par) {
  113.             dfs(child, node);
  114.             if(final_score[child] < min_score) {
  115.                 min_score = final_score[child];
  116.                 curr_node = final_node[child];
  117.             }
  118.             else if(final_score[child] == min_score) {
  119.                 if(curr_node > final_node[child]) {
  120.                     curr_node = final_node[child];
  121.                 }
  122.             }
  123.         }
  124.     }
  125.  
  126.     final_node[node] = curr_node;
  127.     final_score[node] = min_score;
  128. }
  129.  
  130. void run_cases() {
  131.     int n;
  132.     cin >> n;
  133.     vector<int> a(n + 1);
  134.     adj = vector<vector<int>>(n + 1);
  135.     final_score = vector<int>(n + 1);
  136.     initial_score = vector<int>(n + 1);
  137.     transition_score = vector<int>(n + 1);
  138.     final_node = vector<int>(n + 1);
  139.  
  140.     for(int i=1;i<=n;i++) {
  141.         cin >> initial_score[i];
  142.         transition_score[i] = primes[int(upper_bound(all(primes), initial_score[i]) - primes.begin()) - 1];
  143.         final_score[i] = transition_score[i];
  144.         final_node[i] = i;
  145.     }
  146.  
  147.     for(int i=1;i<n;i++) {
  148.         int u,v;
  149.         cin >> u >> v;
  150.         adj[u].push_back(v);
  151.         adj[v].push_back(u);
  152.     }
  153.  
  154.     dfs(1, 1);
  155.  
  156.     for(int i=1;i<=n;i++) {
  157.         cout << final_node[i] << " " << initial_score[i] - final_score[i] << nl;
  158.     }
  159. }
  160.  
  161. int main() {
  162.     ios_base::sync_with_stdio(0); cin.tie(nullptr);
  163.  
  164.     preprocess();
  165.  
  166.     int tests = 1;
  167.     // cin >> tests;
  168.  
  169.     for(int test = 1;test <= tests;test++) {
  170.         run_cases();
  171.     }
  172. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×