Submission #446319

#	Time	Username	Problem	Language	Result	Execution time	Memory
446319		benedict0724	Dynamic Diameter (CEOI19_diameter)	C++17	0 / 100	14 ms	10552 KiB

diameter

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pl;

vector<pair<int, int>> adj[100002];
int st[100002], en[100002], ett[100002], son[100002];
ll cost[100002], v[100002];
int cnt = 0;

void dfs(int x, int p)
{
    ett[++cnt] = x;
    st[x] = cnt;
    for(auto u : adj[x])
    {
        int i = u.first, j = u.second;
        if(i == p) continue;
        dfs(i, x);
        son[j] = i;
        v[i] = v[x] + cost[j];
    }
    en[x] = cnt;
}

struct seg1
{
    vector<int> tree, lazy;
    void init(int i, int l, int r)
    {
        if(l == r) { tree[i] = v[ett[l]]; }
        int m = (l + r)/2;
        init(i*2, l, m); init(i*2+1, m+1, r);
        tree[i] = max(tree[i*2], tree[i*2+1]);
    }
    void INIT(int s, int e)
    {
        tree.resize(4 * (e - s + 1));
        lazy.resize(4 * (e - s + 1));
        init(1, s, e);
    }
    void propagate(int i, int l, int r)
    {
        tree[i] += lazy[i];
        if(l != r)
        {
            lazy[i*2] += lazy[i];
            lazy[i*2+1] += lazy[i];
        }
        lazy[i] = 0;
    }
    void update(int i, int l, int r, int s, int e, ll v)
    {
        propagate(i, l, r);
        if(e < l || r < s) return;
        if(s <= l && r <= e)
        {
            lazy[i] += v;
            propagate(i, l, r);
            return;
        }
        int m = (l + r)/2;
        update(i*2, l, m, s, e, v);
        update(i*2+1, m+1, r, s, e, v);

        tree[i] = max(tree[i*2], tree[i*2+1]);
    }
};

struct seg2
{
    vector<seg1> SEG;
    vector<ll> V; vector<int> ind;
    vector<pair<ll, ll>> tree;
    pair<ll, ll> add(pair<ll, ll> x, pair<ll, ll> y)
    {
        pair<ll, ll> ret;
        ret.first = max(x.first, y.first);
        if(x.first > y.first) ret.second = max(x.second, y.first);
        else ret.second = max(x.first, y.second);

        return ret;
    }
    int siz;
    void init(int i, int l, int r)
    {
        if(l == r) { tree[i] = {V[l], 0}; return; }
        int m = (l + r)/2;
        init(i*2, l, m);
        init(i*2+1, m+1, r);

        tree[i] = add(tree[i*2], tree[i*2+1]);
    }
    void INIT()
    {
        siz = adj[1].size();
        tree.resize(4 * siz);
        V.resize(siz); ind.resize(siz);
        int cnt = 0;
        for(auto u : adj[1])
        {
            int i = u.first;
            seg1 s;
            SEG.push_back(s);
            SEG[cnt].INIT(st[i], en[i]);
            V[cnt] = SEG[cnt].tree[1];
            ind[cnt] = i;
            cnt++;
        }
        init(1, 0, siz-1);
    }

    void update(int i, int l, int r, int idx, ll val)
    {
        if(l == r) { tree[i] = {val, 0}; return; }
        int m = (l + r)/2;
        if(idx <= m) update(i*2, l, m, idx, val);
        else update(i*2+1, m+1, r, idx, val);

        tree[i] = add(tree[i*2], tree[i*2+1]);
    }

    void UPDATE(int d, ll e)
    {
        int l = 0, r = siz-1;
        int Q = son[d];

        ll ch = e - v[Q];
        v[Q] += ch;

        while(l < r)
        {
            int mid = (l + r)/2;
            if(en[ind[mid]] >= en[Q]) r = mid;
            else l = mid + 1;
        }

        SEG[l].update(1, st[ind[l]], en[ind[l]], st[Q], en[Q], ch);
        ll tmp = SEG[l].tree[1];

        update(1, 0, siz-1, l, tmp);
    }

    ll query()
        { return tree[1].first + tree[1].second; }
} ST;

int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL);
    int n, q, w; cin >> n >> q >> w;
    for(int i=0;i<n-1;i++)
    {
        int a, b, c; cin >> a >> b >> c;
        adj[a].push_back({b, i});
        adj[b].push_back({a, i});
        cost[i] = c;
    }
    dfs(1, -1);
    ST.INIT();
    int last = 0;
    for(int i=1;i<=q;i++)
    {
        int d, e; cin >> d >> e;
        d = (d + last)%(n-1);
        e = (e + last)%w;

        ST.UPDATE(d, e);

        last = ST.query();
        cout << last << "\n";
    }
}

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