Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- using namespace std;
- using namespace __gnu_pbds;
- typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- typedef gp_hash_table<int, null_type,hash<int>, equal_to<int>, direct_mask_range_hashing<int>, linear_probe_fn<>,
- hash_standard_resize_policy<hash_exponential_size_policy<>, hash_load_check_resize_trigger<true>,true>> hash_set;
- typedef gp_hash_table<int,null_type> hash_map;
- #define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
- char _;
- #define complete_unique(a) a.erase(unique(a.begin(),a.end()),a.end())
- #define all(a) a.begin(),a.end()
- #define println printf("\n");
- #define readln(x) getline(cin,x);
- #define pb push_back
- #define endl "\n"
- #define INT_INF 0x3f3f3f3f
- #define LL_INF 0x3f3f3f3f3f3f3f3f
- #define EPS 1e-9
- #define MOD 1000000007
- #define MOD2 1494318097
- #define SEED 131
- #define mp make_pair
- #define fastio cin.tie(0); cin.sync_with_stdio(0);
- #define MAXN 400005
- typedef unsigned long long ull;
- typedef long long ll;
- typedef long double ld;
- typedef pair<int,int> pii;
- typedef pair<double,double> pdd;
- typedef pair<ll,ll> pll;
- typedef pair<int,pii> triple;
- typedef int8_t byte;
- const ld PI = (ld)4*atanl(1);
- mt19937 g1(chrono::steady_clock::now().time_since_epoch().count());
- int randint(int a, int b){return uniform_int_distribution<int>(a, b)(g1);}
- ll randlong(ll a,ll b){return uniform_int_distribution<long long>(a, b)(g1);}
- ll gcd(ll a, ll b){return b == 0 ? a : gcd(b, a % b);}
- ll lcm(ll a, ll b){return a*b/gcd(a,b);}
- 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;}
- ll divmod(ll i, ll j, ll mod){i%=mod,j%=mod;return i*fpow(j,mod-2,mod)%mod;}
- struct node{
- int l,r,mn,blocked;
- multiset<int> s;
- };
- int num_nodes,num_edges,num_col,num_q,par[MAXN],vals[MAXN],curr[MAXN],pe[MAXN],cc,tot;
- pii queries[MAXN];
- vector<pair<int,pii>> edges;
- vector<int> ch[MAXN],pos[MAXN];
- vector<pii> adj[MAXN];
- map<int,int> fst[MAXN];
- node seg[4*MAXN];
- inline void push_up(int rt){
- seg[rt].mn = min(seg[rt<<1].mn,seg[rt<<1|1].mn);
- if(seg[rt].blocked)
- seg[rt].mn = INT_MAX;
- }
- void build(int l, int r, int rt){
- seg[rt].l = l, seg[rt].r = r, seg[rt].blocked = false, seg[rt].mn = INT_MAX;
- if(l == r) return;
- int mid = (l+r)/2;
- build(l,mid,rt<<1);
- build(mid+1,r,rt<<1|1);
- }
- void block(int l, int r, int rt, int s){
- if(l > r) return;
- if(seg[rt].l == l && seg[rt].r == r){
- if(s == 0) seg[rt].blocked = true, seg[rt].mn = INT_MAX;
- else{
- seg[rt].blocked = false;
- if(seg[rt].s.size()) seg[rt].mn = *seg[rt].s.begin();
- else seg[rt].mn = INT_MAX;
- }
- return;
- }
- int mid = (seg[rt].l+seg[rt].r)/2;
- if(r <= mid) block(l,r,rt<<1,s);
- else if(l > mid) block(l,r,rt<<1|1,s);
- else block(l,mid,rt<<1,s), block(mid+1,r,rt<<1|1,s);
- push_up(rt);
- }
- void update(int pos, int rt, int val, int s){
- if(s == 0) seg[rt].s.erase(val);
- else seg[rt].s.insert(val);
- if(!seg[rt].blocked){
- if(seg[rt].s.size()) seg[rt].mn = *seg[rt].s.begin();
- else seg[rt].mn = INT_MAX;
- }
- if(seg[rt].l == seg[rt].r) return;
- int mid = (seg[rt].l+seg[rt].r)/2;
- if(pos <= mid) update(pos,rt<<1,val,s);
- else update(pos,rt<<1|1,val,s);
- push_up(rt);
- }
- int query(int pos, int rt){
- if(seg[rt].l == seg[rt].r){
- if(seg[rt].s.empty()) return -1;
- return *seg[rt].s.begin();
- }
- int mid = (seg[rt].l+seg[rt].r)/2;
- if(pos <= mid) return query(pos,rt<<1);
- return query(pos,rt<<1|1);
- }
- void print(){
- for(int i=1; i<=tot; i++)
- printf("%d ",query(i,1));
- printf("\n");
- }
- inline int root(int node){
- while(node != par[node]){
- par[node] = par[par[node]];
- node = par[node];
- }
- return node;
- }
- void dfs(int node, int prev){
- for(pii check:adj[node]){
- if(check.first == prev) continue;
- par[check.first] = node;
- pe[check.first] = check.second;
- ch[node].pb(vals[check.first]);
- tot++;
- dfs(check.first,node);
- }
- }
- void dfs2(int node, int prev){
- for(int i=0; i<ch[node].size(); i++){
- pos[node].pb(++cc);
- if(i == 0 || ch[node][i] != ch[node][i-1])
- fst[node][ch[node][i]] = i;
- }
- for(pii check:adj[node]){
- if(check.first == prev) continue;
- curr[check.first] = pos[node][fst[node][vals[check.first]]];
- update(curr[check.first],1,check.second,1);
- fst[node][vals[check.first]]++;
- }
- for(pii check:adj[node]){
- if(check.first == prev) continue;
- dfs2(check.first,node);
- }
- }
- inline pii fnd(int node, int col){
- int a = lower_bound(all(ch[node]),col)-ch[node].begin();
- int b = upper_bound(all(ch[node]),col)-ch[node].begin()-1;
- return mp(a,b);
- }
- int main(){
- freopen("data.in","r",stdin);
- freopen("data.out","w",stdout);
- // freopen("grass.in","r",stdin);
- // freopen("grass.out","w",stdout);
- scanf("%d %d %d %d",&num_nodes,&num_edges,&num_col,&num_q);
- for(int i=1; i<=num_edges; i++){
- int a,b,c; scanf(" %d %d %d",&a,&b,&c);
- edges.pb(mp(c,mp(a,b)));
- }
- for(int i=1; i<=num_nodes; i++) par[i] = i;
- sort(all(edges));
- for(int i=0; i<edges.size(); i++){
- int a = edges[i].second.first, b = edges[i].second.second, w = edges[i].first;
- int f = root(a), s = root(b);
- if(f == s) continue;
- adj[a].pb(mp(b,w));
- adj[b].pb(mp(a,w));
- par[f] = s;
- }
- for(int i=1; i<=num_nodes; i++)
- scanf(" %d",&vals[i]);
- dfs(1,-1);
- for(int i=1; i<=num_q; i++){
- int a,b; scanf(" %d %d",&a,&b);
- queries[i] = mp(a,b);
- if(a != 1)
- ch[par[a]].pb(b), tot++;
- }
- for(int i=1; i<=num_nodes; i++){
- sort(all(ch[i]));
- // printf("%d: ",i);
- // for(int check:ch[i])
- // printf("%d ",check);
- // printf("\n");
- }
- build(1,tot,1);
- dfs2(1,-1);
- // print();
- for(int i=1; i<=num_q; i++){
- int node = queries[i].first, nv = queries[i].second;
- if(node != 1){
- update(curr[node],1,pe[node],0);
- update(curr[node]=pos[par[node]][fst[par[node]][nv]++],1,pe[node],1);
- }
- pii range = fnd(node,vals[node]);
- if(range.first <= range.second)
- block(pos[node][range.first],pos[node][range.second],1,1);
- range = fnd(node,vals[node]=nv);
- if(range.first <= range.second)
- block(pos[node][range.first],pos[node][range.second],1,0);
- printf("%d\n",seg[1].mn);
- // print();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement