Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
- // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx")
- // #pragma comment(linker, "/stack:200000000"]
- #include <iostream>
- #include <vector>
- #include <cmath>
- #include <algorithm>
- #include <unordered_set>
- #include <unordered_map>
- #include <set>
- #include <map>
- #include <queue>
- #include <deque>
- #include <bitset>
- #include <stack>
- #include <random>
- #include <fstream>
- #include <sstream>
- #include <chrono>
- #define fi first
- #define se second
- #define pb push_back
- #define ll long long
- #define ld long double
- #define hm unordered_map
- #define pii pair<int, int>
- #define sz(a) (int)a.size()
- #define all(a) a.begin(), a.end()
- #define cinv(v) for (auto& x: v) cin >> x
- #define fr(i, n) for (int i = 0; i < n; ++i)
- #define fl(i, l, n) for (int i = l; i < n; ++i)
- // #define int ll
- using namespace std;
- #ifdef __LOCAL
- #define dbg(x) cerr << #x << " : " << x << '\n'
- const int maxn = 2e5 + 20;
- #else
- #define dbg(x)
- const int maxn = 2e5 + 20;
- #endif
- //tg: @galebickosikasa
- ostream& operator << (ostream& out, vector<int>& v) {
- for (auto& x: v) out << x << ' ';
- return out;
- }
- ostream& operator << (ostream& out, pii& v) {
- out << v.fi << ", " << v.se;
- return out;
- }
- ostream& operator << (ostream& out, vector<pii>& v) {
- for (auto& x: v) out << x << '\n';
- return out;
- }
- istream& operator >> (istream& in, pii& a) {
- in >> a.fi >> a.se;
- return in;
- }
- const ll inf = (ll) 2e9;
- const ll kek = 2e18;
- const ld pi = asin (1) * 2;
- const ld eps = 1e-8;
- const ll mod = (ll)1e9 + 7;
- const ll ns = 97;
- const int maxs = 1e6 + 20;
- mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
- multiset<int> answers;
- int parent[maxn], sz[maxn], colors[maxn], pr[maxn], pos[maxn], order[maxn];
- ll dist[maxn];
- vector<pii> g[maxn];
- int j = 0;
- void dfs (int v, int p = -1) {
- parent[v] = p;
- order[j++] = v;
- // dbg (v);
- // dbg (dist[v]);
- sz[v] = 1;
- for (auto& u: g[v]) {
- int to = u.fi, c = u.se;
- if (to == p) continue;
- dist[to] = dist[v] + (ll)c;
- dfs (to, v);
- sz[v] += sz[to];
- }
- }
- struct DSU {
- vector<int> dsu;
- DSU (int s = maxn) {
- dsu = vector<int> (s);
- fr (i, s) dsu[i] = i;
- }
- int get (int x) {
- if (dsu[x] == x) return x;
- return dsu[x] = get (dsu[x]);
- }
- bool join (int a, int b) {
- int x = get (a), y = get (b);
- if (x != y) {
- dsu[x] = y;
- return 1;
- }
- return 0;
- }
- };
- struct edge {
- int a, b, c;
- bool operator < (const edge& other) const {
- return c < other.c;
- }
- };
- vector<edge> edges;
- struct Tree {
- Tree* left;
- Tree* right;
- int priority, color, mx, mn;
- ll value;
- Tree (ll d, int x) {
- left = right = nullptr;
- priority = rnd ();
- value = d;
- color = mx = mn = x;
- }
- };
- int get_mn (Tree* t) {
- if (t == nullptr) return inf;
- return t->mn;
- }
- int get_mx (Tree* t) {
- if (t == nullptr) return -inf;
- return t->mx;
- }
- ll get_val (Tree* t) {
- if (t == nullptr) return -1;
- return t->value;
- }
- void render (Tree* t) {
- if (t == nullptr) return;
- t->mx = max (t->color, max (get_mx (t->left), get_mx (t->right)));
- t->mn = min (t->color, min (get_mn (t->left), get_mn (t->right)));
- }
- Tree* merge (Tree* l, Tree* r) {
- if (l == nullptr) return r;
- if (r == nullptr) return l;
- if (l->priority > r->priority) {
- l->right = merge (l->right, r);
- render (l);
- return l;
- } else {
- r->left = merge (l, r->left);
- render (r);
- return r;
- }
- }
- pair<Tree*, Tree*> split (Tree* t, ll x) {
- pair<Tree*, Tree*> ptt = {nullptr, nullptr};
- if (t == nullptr) return ptt;
- if (t->value > x) {
- ptt = split (t->left, x);
- t->left = ptt.se;
- ptt.se = t;
- } else {
- ptt = split (t->right, x);
- t->right = ptt.fi;
- ptt.fi = t;
- }
- render (t);
- return ptt;
- }
- Tree* erase (Tree* t, ll d, int x) {
- if (t == nullptr) return t;
- if (t->value == d && t->color == x) return merge (t->left, t->right);
- if (t->value > d) t->left = erase (t->left, d, x);
- else t->right = erase (t->right, d, x);
- render (t);
- return t;
- }
- Tree* add (Tree* t, Tree* a) {
- auto ptt = split (t, a->value);
- ptt.fi = merge (ptt.fi, a);
- return merge (ptt.fi, ptt.se);
- }
- Tree* add (Tree* t, ll d, int x) {
- Tree* a = new Tree (d, x);
- return add (t, a);
- }
- // void dfs (Tree* t) {
- // if (t == nullptr) return;
- // dfs (t->left);
- // dbg (t->value);
- // dbg (t->color);
- // dfs (t->right);
- // }
- ll down (Tree* t, int new_color) {
- if (t == nullptr || (t->mn == new_color && t->mx == new_color)) return kek;
- ll ans = kek;
- // dbg (t->value);
- // dfs (t);
- // dbg ("exit");
- // dbg (get_val (t->left));
- // dbg (get_val (t->right));
- if (t->color != new_color) ans = t->value;
- if (get_mn (t->left) == inf || (get_mn (t->left) == new_color && get_mx (t->left) == new_color)) {
- ans = min (ans, down (t->right, new_color));
- // dbg ("right");
- // dbg (ans);
- return ans;
- }
- ans = min (ans, down (t->left, new_color));
- // dbg ("left");
- // dbg (ans);
- return ans;
- }
- struct ST {
- vector<Tree*> t;
- int size = 0, capacity;
- ST (int s = maxn) {
- while ((1<<size) < s) ++size;
- ++size;
- size = (1<<size);
- capacity = (size>>1);
- t = vector<Tree*> (size, nullptr);
- vector<vector<pii>> tmp (size);
- fr (i, j) {
- tmp[i + capacity].pb ({dist[order[i]], colors[order[i]]});
- t[i + capacity] = add (t[i + capacity], dist[order[i]], colors[order[i]]);
- }
- for (int i = capacity - 1; i > 0; --i) {
- for (auto& x: tmp[i * 2]) tmp[i].pb (x);
- for (auto& x: tmp[i * 2 + 1]) tmp[i].pb (x);
- // dbg (i);
- // dbg (tmp[i]);
- for (auto& x: tmp[i]) t[i] = add (t[i], x.fi, x.se);
- }
- }
- ll upd (int cur, int left, int right, int l, int r, int new_color) {
- if (cur >= size) return kek;
- if (left > r || right < l) return kek;
- if (l <= left && r >= right) {
- // dbg ("open");
- // dbg (cur);
- return down (t[cur], new_color);
- }
- return min (upd (cur * 2, left, (left + right) / 2, l, r, new_color), upd (cur * 2 + 1, (left + right) / 2 + 1, right, l, r, new_color));
- }
- ll upd (int l, int r, int new_color) {
- return upd (1, 0, capacity - 1, l, r, new_color);
- }
- void upd (int v, int new_color) {
- if (v < 0) {
- v *= -1;
- ll x = upd (pos[v] + 1, pos[v] + sz[v] - 1, new_color) - dist[v];
- int p = pr[v];
- if (p < inf) {
- auto it = answers.find (p);
- if (it != answers.end ()) answers.erase (it);
- }
- if (x + dist[v] < inf) answers.insert (x), pr[v] = x;
- return;
- }
- if (sz[v] <= 1) {
- int u = pos[v] + capacity;
- // dbg (u);
- int p = colors[v];
- while (u) {
- // dbg ("here");
- // dfs (t[u]);
- t[u] = erase (t[u], dist[v], p);
- // dbg (dist[v]);
- // dbg (p);
- // dbg ("cont");
- // dfs (t[u]);
- t[u] = add (t[u], dist[v], new_color);
- // dbg ("end");
- // dfs (t[u]);
- u /= 2;
- }
- return;
- }
- int u = pos[v] + capacity;
- // dbg (u);
- int p = colors[v];
- while (u) {
- // dbg ("here");
- // dfs (t[u]);
- t[u] = erase (t[u], dist[v], p);
- // dbg (dist[v]);
- // dbg (p);
- // dbg ("cont");
- // dfs (t[u]);
- t[u] = add (t[u], dist[v], new_color);
- // dbg ("end");
- // dfs (t[u]);
- u /= 2;
- }
- ll x = upd (pos[v] + 1, pos[v] + sz[v] - 1, new_color) - dist[v];
- // dbg (v);
- // dbg (x);
- p = pr[v];
- // dbg (p);
- if (p < inf) {
- auto it = answers.find (p);
- if (it != answers.end ()) answers.erase (it);
- }
- if (x + dist[v] < inf) answers.insert (x), pr[v] = x;
- }
- };
- signed main () {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- int n, m, d, q;
- cin >> n >> m >> d >> q;
- fr (i, m) {
- int a, b, c;
- cin >> a >> b >> c;
- edges.pb ({a, b, c});
- }
- sort (all (edges));
- DSU dsu (n + 1);
- for (auto& e: edges) {
- if (dsu.join (e.a, e.b)) {
- g[e.a].pb ({e.b, e.c}), g[e.b].pb ({e.a, e.c});
- }
- }
- dfs (1);
- // fr (i, n) dbg (dist[i + 1]);
- // dbg (order);
- fr (i, j) {
- pos[order[i]] = i;
- }
- fr (i, n) {
- int x;
- cin >> x;
- colors[i + 1] = x;
- }
- for (auto& x: pr) x = inf;
- ST goo (n + 1);
- fr (i, n) goo.upd (i + 1, colors[i + 1]);
- // for (auto& x: answers) dbg (x);
- // dbg ("BEGIN");
- fr (i, q) {
- int v, x;
- cin >> v >> x;
- goo.upd (v, x);
- colors[v] = x;
- if (parent[v] != -1) goo.upd (-parent[v], colors[parent[v]]);
- cout << *answers.begin () << '\n';
- // dbg ("NEXT");
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement