Submission #1165188

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165188		Warinchai	Dynamic Diameter (CEOI19_diameter)	C++20	100 / 100	265 ms	107772 KiB

diameter

#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int> adj[800005];
int ar[800005];
int n, q, w;
struct path
{
    int l, d, mxpre, mxsuf;
    path(int x = 0)
    {
        l = d = mxpre = mxsuf = x;
    }
    friend path operator+(path &a, path &b)
    {
        path c;
        c.l = a.l + b.l;
        c.mxsuf = max(b.mxsuf, a.mxsuf + b.l);
        c.mxpre = max(a.mxpre, b.mxpre + a.l);
        c.d = max({a.d, b.d, a.mxsuf + b.mxpre});
        return c;
    }
} paths[1000005];
struct point
{
    int mx, d;
    point(int x = 0)
    {
        mx = d = x;
    }
    friend point operator+(point &a, point &b)
    {
        point c;
        c.mx = max(a.mx, b.mx);
        c.d = max({a.d, b.d, a.mx + b.mx});
        return c;
    }
} points[1000005];
vector<pair<int, int>> l, r;
struct sttttree
{
    int sz[800005], hv[800005], l[800005], r[800005], p[800005], type[800005], pa[800005];
    int cur = 0, rt;
    void dfs(int u, int p)
    {
        pa[u] = p;
        sz[u] = 1;
        for (auto x : adj[u])
        {
            if (x == p)
                continue;
            dfs(x, u);
            sz[u] += sz[x];
            if (sz[x] > sz[hv[u]])
                hv[u] = x;
        }
    }
    void build(int x)
    {
        dfs(x, 0);
        cur = n + n - 1;
        rt = compress(x).first;
    }
    int add(int t, int lch, int rch, int ty)
    {
        if (t == 0)
            t = ++cur;
        type[t] = ty;
        // cerr<<t<<" "<<lch<<"\n";
        if (lch)
            p[lch] = t;
        if (rch)
            p[rch] = t;
        l[t] = lch, r[t] = rch;
        return t;
    }
    pair<int, int> merge(vector<pair<int, int>> &v, int type)
    {
        if (v.size() == 1)
            return v[0];
        int sz = 0;
        vector<pair<int, int>> l, r;
        for (auto x : v)
        {
            sz += x.second;
        }
        for (auto x : v)
        {
            if (x.second <= sz)
                l.push_back(x);
            else
                r.push_back(x);
            sz -= 2 * x.second;
        }
        auto a = merge(l, type);
        auto b = merge(r, type);
        l.clear();
        r.clear();
        return {add(0, a.first, b.first, type), a.second + b.second};
    }
    pair<int, int> compress(int x)
    {
        // cerr<<"compress:"<<x<<"\n";
        vector<pair<int, int>> v;
        for (; x; x = hv[x])
            v.push_back(add_vertex(x));
        // for(auto x:v)cerr<<x.first<<" "<<x.second<<"\n";
        // cerr<<"compress con:"<<v[0].first<<"\n";
        return merge(v, 1);
    }
    pair<int, int> add_vertex(int x)
    {
        // cerr<<"add_vertex:"<<x<<"\n";
        pair<int, int> v = rake(x);
        // cerr<<"add vertex con:"<<v.first<<" "<<v.second<<"\n";
        pair<int, int> ans = {add(x, v.first, 0, v.second == 0 ? 3 : 2), v.second + 1};
        // cerr<<"added ver:"<<ans.first<<" "<<ans.second<<"\n";
        return ans;
    }
    pair<int, int> rake(int x)
    {
        // cerr<<"rake:"<<x<<"\n";
        vector<pair<int, int>> v;
        for (auto a : adj[x])
            if (a != hv[x] && a != pa[x])
                v.push_back(add_edge(a));
        if (v.size() == 0)
            return {0, 0};
        return merge(v, 4);
    }
    pair<int, int> add_edge(int x)
    {
        // cerr<<"add edge"<<x<<"\n";
        pair<int, int> v = compress(x);
        return {add(0, v.first, 0, 5), v.second};
    }
} tr;
path compress(path a, path b)
{
    return a + b;
}
path add_vertex(point x, int val)
{
    path a;
    a.l = val;
    a.mxpre = a.mxsuf = x.mx + val;
    a.d = max(x.d, val + x.mx);
    return a;
}
path vertex(int x)
{
    path a(x);
    return a;
}
point rake(point a, point b)
{
    return a + b;
}
point add_edge(path a)
{
    point x;
    x.mx = a.mxpre, x.d = a.d;
    return x;
}
void upd(int u, int t)
{
    if (t == 1)
    {
        paths[u] = compress(paths[tr.l[u]], paths[tr.r[u]]);
    }
    else if (t == 2)
    {
        paths[u] = add_vertex(points[tr.l[u]], ar[u]);
    }
    else if (t == 3)
    {
        paths[u] = vertex(ar[u]);
    }
    else if (t == 4)
    {
        points[u] = rake(points[tr.l[u]], points[tr.r[u]]);
    }
    else
    {
        points[u] = add_edge(paths[tr.l[u]]);
    }
}
void change(int u)
{
    for (; u; u = tr.p[u])
        upd(u, tr.type[u]);
}
void dfs(int u)
{
    if (tr.l[u])
        dfs(tr.l[u]);
    if (tr.r[u])
        dfs(tr.r[u]);
    upd(u, tr.type[u]);
    // cout<<u<<" ";
    /*if(tr.type[u]<=3){
        cout<<"paths:"<<paths[u].d<<" "<<paths[u].l<<" "<<paths[u].mxpre<<" "<<paths[u].mxsuf<<"\n";
    }else{
        cout<<"points:"<<points[u].d<<" "<<points[u].mx<<"\n";
    }
    if(u==11)cout<<"11:"<<tr.l[u]<<" "<<tr.r[u]<<" "<<tr.type[u]<<"\n";*/
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q >> w;
    int cur = n;
    for (int i = 1; i < n; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back(++cur);
        adj[cur].push_back(a);
        adj[b].push_back(cur);
        adj[cur].push_back(b);
        ar[cur] = c;
    }
    // cerr<<"work\n";
    tr.build(1);
    // printt(tr.rt);
    // cerr<<"work\n";
    dfs(tr.rt);
    // cerr<<"ANS:\n";
    // cerr<<paths[tr.rt].d<<"\n";
    int last = 0;
    // cerr<<"still work\n";
    for (int i = 0; i < q; i++)
    {
        int d, e;
        cin >> d >> e;
        d = (d + last) % (n - 1);
        e = (e + last) % w;
        ar[d + n + 1] = e;
        change(d + n + 1);
        // dfs(tr.rt);
        cout << (last = paths[tr.rt].d) << "\n";
    }
}

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