Submission #1104750

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104750		Ali_BBN	Dynamic Diameter (CEOI19_diameter)	C++14	100 / 100	3863 ms	44728 KiB

diameter

#include <bits/stdc++.h>
#define mp make_pair
#define ll long long
#define migmig cin.tie(NULL);ios_base::sync_with_stdio(false)
#define max_heap(T) priority_queue<T>
#define min_heap(T) priority_queue<T, vector<T>, greater<T>>
#define pb push_back
#define fi first
#define sec second
#define endl "\n"
#define pii pair <int, ll>
using namespace std;
const ll MOD = 1e9 + 7;
const int INF = 1e9;
const ll INF18 = 6e18;
const int MAXN = 1e5 + 1;
const int LOG = 23;
const int TEST = 25;
bool visited[MAXN];
int st[MAXN], ft[MAXN], timee = 0;
vector <pii> adj[MAXN];
int par[MAXN];
ll a[MAXN], b[MAXN], n, lzy[4 * MAXN];
pair <ll, int> node[4 * MAXN];
int sts[MAXN];
int fuck[MAXN][TEST];
int nf[TEST];
int h[MAXN];
void dfs(int r){
    int t = 0;
    if (h[r] < TEST) nf[h[r]] = r;
    visited[r] = 1, sts[timee] = r, st[r] = timee++;
    for (auto i : adj[r]){
        if (visited[i.fi] == 0){
            t++;
            par[i.fi] = r;
            h[i.fi] = h[r] + 1;
            b[i.fi] = b[r] + i.sec;
            dfs(i.fi);
        }
    }
    ft[r] = timee;
    for (int i = 0; i <= min(h[r], TEST - 1); i++) fuck[r][i] = nf[i];
}
void build(int l = 0, int r = n, int id = 1){
	if (l + 1 == r) node[id] = mp(a[l], l), lzy[id] = 0;
	else{
		int mid = (l + r) / 2;
		build(l, mid, id * 2);
		build(mid, r, id * 2 + 1);
		if (node[id * 2].fi > node[id * 2 + 1].fi) node[id] = node[id * 2];
        else node[id] = node[id * 2 + 1];
        lzy[id] = 0;
	}
}
pair <ll, int> get(int s, int e, int l = 0, int r = n, int id = 1){
	if (s <= l && e >= r) return node[id];
	if (s >= r || e <= l) return mp(0, l);
	int mid = (l + r) / 2;
    lzy[id * 2] += lzy[id];
    lzy[id * 2 + 1] += lzy[id];
    node[id * 2].fi += lzy[id];
    node[id * 2 + 1].fi += lzy[id];
    lzy[id] = 0;
    auto g1 = get(s, e, l, mid, id * 2), g2 = get(s, e, mid, r, id * 2 + 1);
    if (g1.fi > g2.fi) return g1;
    else return g2;
}
void upd(int s, int e, ll x, int l = 0, int r = n, int id = 1){
	if (s <= l && e >= r){
        lzy[id] += x, node[id].fi += x;
        return;
    }
	if (s >= r || e <= l) return;
	int mid = (l + r) / 2;
    lzy[id * 2] += lzy[id];
    lzy[id * 2 + 1] += lzy[id];
    node[id * 2].fi += lzy[id];
    node[id * 2 + 1].fi += lzy[id];
    lzy[id] = 0;
    upd(s, e, x, l, mid, id * 2);
    upd(s, e, x, mid, r, id * 2 + 1);
    if (node[id * 2].fi > node[id * 2 + 1].fi) node[id] = node[id * 2];
    else node[id] = node[id * 2 + 1];
}
void solve(){
    ll q, w;
    cin >> n >> q >> w;
    vector <pair <pair <int, int>, ll> > y;
    for (int i = 0; i < n - 1; i++){
        ll u, v, w;
        cin >> u >> v >> w;
        adj[u].pb(mp(v, w));
        adj[v].pb(mp(u, w));
        y.pb(mp(mp(u, v), w));
    }
    dfs(1);
    for (int i = 1; i <= n; i++) a[st[i]] = b[i];
    build();
    if (n <= 5000 && q <= 5000){
        ll last = 0;
        for (int i = 0; i < q; i++){
            ll d, e;
            cin >> d >> e;
            d = (d + last) % (n - 1);
            e = (e + last) % w;
            auto [u, v] = y[d].fi;
            ll w1 = y[d].sec;
            y[d].sec = e;
            if (st[u] > st[v]) swap(u, v);
            upd(st[v], ft[v], e - w1);
            pair <ll, int> g = get(0, n);
            int f = sts[g.sec];
            ll maax = g.fi;
            while (f != 1){
                int u = par[f];
                for (auto i : adj[u]){
                    if (i.fi != f && i.fi != par[u]){
                        maax = max(maax, g.fi + (get(st[i.fi], ft[i.fi]).fi) - get(st[u], st[u] + 1).fi * 2);
                    }
                }
                f = u;
            }
            cout << maax << endl;
            last = maax;
        }
    }
    else{
        ll last = 0;
        for (int i = 0; i < q; i++){
            ll d, e;
            cin >> d >> e;
            d = (d + last) % (n - 1);
            e = (e + last) % w;
            auto [u, v] = y[d].fi;
            ll w1 = y[d].sec;
            y[d].sec = e;
            if (st[u] > st[v]) swap(u, v);
            upd(st[v], ft[v], e - w1);
            pair <ll, int> g = get(0, n);
            int f = sts[g.sec];
            ll maax = g.fi;
            int num = 0;
            while (f != 1 && num < TEST){
                int u = par[f];
                upd(st[f], ft[f], -INF18);
                maax = max(maax, get(st[u], ft[u]).fi + g.fi - get(st[u], st[u] + 1).fi * 2);
                upd(st[f], ft[f], INF18);
                f = u;
                num++;
            }
            f = sts[g.sec];
            for (int i = 0; i < min(h[f] - 1, TEST - 1); i++){
                int u = fuck[f][i], v = fuck[f][i + 1];
                upd(st[v], ft[v], -INF18);
                maax = max(maax, get(st[u], ft[u]).fi + g.fi - get(st[u], st[u] + 1).fi * 2);
                upd(st[v], ft[v], INF18);
            }
            cout << maax << endl;
            last = maax;
        }
    }
}
int main(){
	migmig;
	int tc = 1;
	// cin >> tc;
	for (int ti = 0; ti < tc; ti++) solve();
}

Compilation message (stderr)

diameter.cpp: In function 'void solve()':
diameter.cpp:107:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  107 |             auto [u, v] = y[d].fi;
      |                  ^
diameter.cpp:135:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  135 |             auto [u, v] = y[d].fi;
      |                  ^

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 27 / 27