SHARE
TWEET

Untitled

a guest Jan 22nd, 2020 79 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
  9. typedef gp_hash_table<int, null_type,hash<int>, equal_to<int>, direct_mask_range_hashing<int>, linear_probe_fn<>,
  10.     hash_standard_resize_policy<hash_exponential_size_policy<>, hash_load_check_resize_trigger<true>,true>> hash_set;
  11. typedef gp_hash_table<int,null_type> hash_map;
  12.  
  13. #define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
  14. char _;
  15. #define complete_unique(a) a.erase(unique(a.begin(),a.end()),a.end())
  16. #define all(a) a.begin(),a.end()
  17. #define println printf("\n");
  18. #define readln(x) getline(cin,x);
  19. #define pb push_back
  20. #define endl "\n"
  21. #define INT_INF 0x3f3f3f3f
  22. #define LL_INF 0x3f3f3f3f3f3f3f3f
  23. #define EPS 1e-9
  24. #define MOD 1000000007
  25. #define MOD2 1494318097
  26. #define SEED 131
  27. #define mp make_pair
  28. #define fastio cin.tie(0); cin.sync_with_stdio(0);
  29.  
  30. #define MAXN 400005
  31.  
  32. typedef unsigned long long ull;
  33. typedef long long ll;
  34. typedef long double ld;
  35. typedef pair<int,int> pii;
  36. typedef pair<double,double> pdd;
  37. typedef pair<ll,ll> pll;
  38. typedef pair<int,pii> triple;
  39. typedef int8_t byte;
  40.  
  41. const ld PI = (ld)4*atanl(1);
  42.  
  43. mt19937 g1(chrono::steady_clock::now().time_since_epoch().count());
  44.  
  45. int randint(int a, int b){return uniform_int_distribution<int>(a, b)(g1);}
  46. ll randlong(ll a,ll b){return uniform_int_distribution<long long>(a, b)(g1);}
  47.  
  48. ll gcd(ll a, ll b){return b == 0 ? a : gcd(b, a % b);}
  49. ll lcm(ll a, ll b){return a*b/gcd(a,b);}
  50. ll fpow(ll  b, ll exp, ll mod){if(exp == 0) return 1;ll t = fpow(b,exp/2,mod);if(exp&1) return t*t%mod*b%mod;return t*t%mod;}
  51. ll divmod(ll i, ll j, ll mod){i%=mod,j%=mod;return i*fpow(j,mod-2,mod)%mod;}
  52.  
  53. struct node{
  54.     int l,r,mn,blocked;
  55.     multiset<int> s;
  56. };
  57.  
  58. int num_nodes,num_edges,num_col,num_q,par[MAXN],vals[MAXN],curr[MAXN],pe[MAXN],cc,tot;
  59. pii queries[MAXN];
  60. vector<pair<int,pii>> edges;
  61. vector<int> ch[MAXN],pos[MAXN];
  62. vector<pii> adj[MAXN];
  63. map<int,int> fst[MAXN];
  64. node seg[4*MAXN];
  65.  
  66. inline void push_up(int rt){
  67.     seg[rt].mn = min(seg[rt<<1].mn,seg[rt<<1|1].mn);
  68.     if(seg[rt].blocked)
  69.         seg[rt].mn = INT_MAX;
  70. }
  71.  
  72. void build(int l, int r, int rt){
  73.     seg[rt].l = l, seg[rt].r = r, seg[rt].blocked = false, seg[rt].mn = INT_MAX;
  74.     if(l == r) return;
  75.     int mid = (l+r)/2;
  76.     build(l,mid,rt<<1);
  77.     build(mid+1,r,rt<<1|1);
  78. }
  79.  
  80. void block(int l, int r, int rt, int s){
  81.     if(l > r) return;
  82.     if(seg[rt].l == l && seg[rt].r == r){
  83.         if(s == 0) seg[rt].blocked = true, seg[rt].mn = INT_MAX;
  84.         else{
  85.             seg[rt].blocked = false;
  86.             if(seg[rt].s.size()) seg[rt].mn = *seg[rt].s.begin();
  87.             else seg[rt].mn = INT_MAX;
  88.         }
  89.         return;
  90.     }
  91.     int mid = (seg[rt].l+seg[rt].r)/2;
  92.     if(r <= mid) block(l,r,rt<<1,s);
  93.     else if(l > mid) block(l,r,rt<<1|1,s);
  94.     else block(l,mid,rt<<1,s), block(mid+1,r,rt<<1|1,s);
  95.     push_up(rt);
  96. }
  97.  
  98. void update(int pos, int rt, int val, int s){
  99.     if(s == 0) seg[rt].s.erase(val);
  100.     else seg[rt].s.insert(val);
  101.     if(!seg[rt].blocked){
  102.         if(seg[rt].s.size()) seg[rt].mn = *seg[rt].s.begin();
  103.         else seg[rt].mn = INT_MAX;
  104.     }
  105.     if(seg[rt].l == seg[rt].r) return;
  106.     int mid = (seg[rt].l+seg[rt].r)/2;
  107.     if(pos <= mid) update(pos,rt<<1,val,s);
  108.     else update(pos,rt<<1|1,val,s);
  109.     push_up(rt);
  110. }
  111.  
  112. int query(int pos, int rt){
  113.     if(seg[rt].l == seg[rt].r){
  114.         if(seg[rt].s.empty()) return -1;
  115.         return *seg[rt].s.begin();
  116.     }
  117.     int mid = (seg[rt].l+seg[rt].r)/2;
  118.     if(pos <= mid) return query(pos,rt<<1);
  119.     return query(pos,rt<<1|1);
  120. }
  121.  
  122. void print(){
  123.     for(int i=1; i<=tot; i++)
  124.         printf("%d ",query(i,1));
  125.     printf("\n");
  126. }
  127.  
  128. inline int root(int node){
  129.     while(node != par[node]){
  130.         par[node] = par[par[node]];
  131.         node = par[node];
  132.     }
  133.     return node;
  134. }
  135.  
  136. void dfs(int node, int prev){
  137.     for(pii check:adj[node]){
  138.         if(check.first == prev) continue;
  139.         par[check.first] = node;
  140.         pe[check.first] = check.second;
  141.         ch[node].pb(vals[check.first]);
  142.         tot++;
  143.         dfs(check.first,node);
  144.     }
  145. }
  146.  
  147. void dfs2(int node, int prev){
  148.     for(int i=0; i<ch[node].size(); i++){
  149.         pos[node].pb(++cc);
  150.         if(i == 0 || ch[node][i] != ch[node][i-1])
  151.             fst[node][ch[node][i]] = i;
  152.     }
  153.     for(pii check:adj[node]){
  154.         if(check.first == prev) continue;
  155.         curr[check.first] = pos[node][fst[node][vals[check.first]]];
  156.         update(curr[check.first],1,check.second,1);
  157.         fst[node][vals[check.first]]++;
  158.     }
  159.     for(pii check:adj[node]){
  160.         if(check.first == prev) continue;
  161.         dfs2(check.first,node);
  162.     }
  163. }
  164.  
  165. inline pii fnd(int node, int col){
  166.     int a = lower_bound(all(ch[node]),col)-ch[node].begin();
  167.     int b = upper_bound(all(ch[node]),col)-ch[node].begin()-1;
  168.     return mp(a,b);
  169. }
  170.  
  171. int main(){
  172.     freopen("data.in","r",stdin);
  173.     freopen("data.out","w",stdout);
  174. //    freopen("grass.in","r",stdin);
  175. //    freopen("grass.out","w",stdout);
  176.     scanf("%d %d %d %d",&num_nodes,&num_edges,&num_col,&num_q);
  177.     for(int i=1; i<=num_edges; i++){
  178.         int a,b,c; scanf(" %d %d %d",&a,&b,&c);
  179.         edges.pb(mp(c,mp(a,b)));
  180.     }
  181.     for(int i=1; i<=num_nodes; i++) par[i] = i;
  182.     sort(all(edges));
  183.     for(int i=0; i<edges.size(); i++){
  184.         int a = edges[i].second.first, b = edges[i].second.second, w = edges[i].first;
  185.         int f = root(a), s = root(b);
  186.         if(f == s) continue;
  187.         adj[a].pb(mp(b,w));
  188.         adj[b].pb(mp(a,w));
  189.         par[f] = s;
  190.     }
  191.     for(int i=1; i<=num_nodes; i++)
  192.         scanf(" %d",&vals[i]);
  193.     dfs(1,-1);
  194.     for(int i=1; i<=num_q; i++){
  195.         int a,b; scanf(" %d %d",&a,&b);
  196.         queries[i] = mp(a,b);
  197.         if(a != 1)
  198.             ch[par[a]].pb(b), tot++;
  199.     }
  200.     for(int i=1; i<=num_nodes; i++){
  201.         sort(all(ch[i]));
  202. //        printf("%d: ",i);
  203. //        for(int check:ch[i])
  204. //            printf("%d ",check);
  205. //        printf("\n");
  206.     }
  207.     build(1,tot,1);
  208.     dfs2(1,-1);
  209. //    print();
  210.     for(int i=1; i<=num_q; i++){
  211.         int node = queries[i].first, nv = queries[i].second;
  212.         if(node != 1){
  213.             update(curr[node],1,pe[node],0);
  214.             update(curr[node]=pos[par[node]][fst[par[node]][nv]++],1,pe[node],1);
  215.         }
  216.         pii range = fnd(node,vals[node]);
  217.         if(range.first <= range.second)
  218.             block(pos[node][range.first],pos[node][range.second],1,1);
  219.         range = fnd(node,vals[node]=nv);
  220.         if(range.first <= range.second)
  221.             block(pos[node][range.first],pos[node][range.second],1,0);
  222.         printf("%d\n",seg[1].mn);
  223. //        print();
  224.     }
  225. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top