Submission #1207146

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207146		Hanksburger	Dynamic Diameter (CEOI19_diameter)	C++20	100 / 100	3237 ms	270200 KiB

diameter

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct node
{
    node *lc, *rc;
    int l, r;
    int mx, lazy;
    node(int l, int r) : lc(0), rc(0), l(l), r(r), mx(0), lazy(0) {}
};
void push(node *i)
{
    if (!i->lazy)
        return;
    int mid=(i->l+i->r)/2;
    if (!i->lc)
        i->lc=new node(i->l, mid);
    if (!i->rc)
        i->rc=new node(mid+1, i->r);
    i->lc->mx+=i->lazy;
    i->lc->lazy+=i->lazy;
    i->rc->mx+=i->lazy;
    i->rc->lazy+=i->lazy;
    i->lazy=0;
}
void update(node *i, int ql, int qr, int x)
{
    //cout << "update " << (i->l) << ' ' << (i->r) << ' ' << ql << ' ' << qr << ' ' << x << '\n';
    if (ql<=i->l && i->r<=qr)
    {
        i->mx+=x;
        i->lazy+=x;
        return;
    }
    push(i);
    int mid=(i->l+i->r)/2;
    if (i->l<=qr && ql<=mid)
    {
        if (!i->lc)
            i->lc=new node(i->l, mid);
        update(i->lc, ql, qr, x);
    }
    if (mid<qr && ql<=i->r)
    {
        if (!i->rc)
            i->rc=new node(mid+1, i->r);
        update(i->rc, ql, qr, x);
    }
    i->mx=max(i->lc?i->lc->mx:0, i->rc?i->rc->mx:0);
}
vector<pair<pair<int, int>, pair<int, int> > > edge[100005];
vector<pair<int, int> > adj[100005];
multiset<int> s[100005], ss;
vector<node*> seg[100005];
int weight[100005];
void dfs1(unordered_map<int, int> &mp, vector<int> &sz, int u, int p)
{
    for (int i=0; i<adj[u].size(); i++)
    {
        int v=adj[u][i].first;
        if (v==p || !mp[v])
            continue;
        dfs1(mp, sz, v, u);
        sz[mp[u]]+=sz[mp[v]];
    }
}
int dfs2(unordered_map<int, int> &mp, vector<int> &sz, int u, int p, int n)
{
    for (int i=0; i<adj[u].size(); i++)
    {
        int v=adj[u][i].first;
        if (v==p || !mp[v])
            continue;
        if (sz[mp[v]]*2>n)
            return dfs2(mp, sz, v, u, n);
    }
    return u;
}
void dfs3(unordered_map<int, int> &mp, vector<int> &tin, vector<int> &tout, int u, int p, int &t)
{
    tin[mp[u]]=++t;
    for (int i=0; i<adj[u].size(); i++)
    {
        int v=adj[u][i].first;
        if (v==p || !mp[v])
            continue;
        dfs3(mp, tin, tout, v, u, t);
    }
    tout[mp[u]]=t;
}
void dfs4(unordered_map<int, int> &mp, vector<int> &tmp, vector<int> &tin, vector<int> &tout, int u, int p, int centroid)
{
    tmp.push_back(u);
    for (int i=0; i<adj[u].size(); i++)
    {
        int v=adj[u][i].first, w=adj[u][i].second;
        if (v==p || !mp[v])
            continue;
        edge[w].push_back({{centroid, seg[centroid].size()}, {tin[mp[v]], tout[mp[v]]}});
        dfs4(mp, tmp, tin, tout, v, u, centroid);
    }
}
void recur(vector<int> &vec)
{
    if (vec.size()==1)
        return;
    /*cout << "recur ";
    for (int u:vec)
        cout << u << ' ';
    cout << '\n';*/
    vector<int> sz(vec.size()+1, 1), tin(vec.size()+1), tout(vec.size()+1);
    unordered_map<int, int> mp;
    for (int i=0; i<vec.size(); i++)
        mp[vec[i]]=i+1;
    dfs1(mp, sz, vec[0], 0);
    int centroid=dfs2(mp, sz, vec[0], 0, vec.size()), t=0;
    dfs3(mp, tin, tout, centroid, 0, t);
    for (int i=0; i<adj[centroid].size(); i++)
    {
        int v=adj[centroid][i].first, w=adj[centroid][i].second;
        if (!mp[v])
            continue;
        edge[w].push_back({{centroid, seg[centroid].size()}, {tin[mp[v]], tout[mp[v]]}});
        //cout << "edge " << w << " push " << centroid << ' ' << seg[centroid].size() << ' ' << tin[mp[v]] << ' ' << tout[mp[v]] << '\n';
        vector<int> tmp;
        dfs4(mp, tmp, tin, tout, v, centroid, centroid);
        recur(tmp);
        seg[centroid].push_back(new node(tin[mp[v]], tout[mp[v]]));
        //cout << "seg " << centroid << ' ' << seg[centroid].size()-1 << " has range " << tin[mp[v]] << ' ' << tout[mp[v]] << '\n';
        s[centroid].insert(0);
    }
    ss.insert(0);
    /*cout << "done recur ";
    for (int u:vec)
        cout << u << ' ';
    cout << '\n';*/
}
void update(int ind, int x)
{
    //cout << "update " << ind << ' ' << x << '\n';
    for (int i=0; i<edge[ind].size(); i++)
    {
        int centroid=edge[ind][i].first.first, num=edge[ind][i].first.second, l=edge[ind][i].second.first, r=edge[ind][i].second.second;
        //cout << "ss erase " << (s[centroid].size()==1?*s[centroid].begin():*s[centroid].begin()+*next(s[centroid].begin())) << '\n';
        ss.erase(ss.find(s[centroid].size()==1?*s[centroid].begin():*s[centroid].begin()+*next(s[centroid].begin())));
        //cout << "s erase " << (*s[centroid].find(-seg[centroid][num]->mx)) << '\n';
        s[centroid].erase(s[centroid].find(-seg[centroid][num]->mx));
        //cout << "here\n";
        update(seg[centroid][num], l, r, x);
        s[centroid].insert(-seg[centroid][num]->mx);
        //cout << "s insert " << (-seg[centroid][num]->mx) << '\n';
        ss.insert(s[centroid].size()==1?*s[centroid].begin():*s[centroid].begin()+*next(s[centroid].begin()));
        //cout << "ss insert " << (s[centroid].size()==1?*s[centroid].begin():*s[centroid].begin()+*next(s[centroid].begin())) << '\n';
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, q, r, ans=0;
    cin >> n >> q >> r;
    for (int i=0; i<n-1; i++)
    {
        int u, v;
        cin >> u >> v >> weight[i];
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }
    vector<int> tmp;
    for (int i=1; i<=n; i++)
        tmp.push_back(i);
    recur(tmp);
    for (int i=0; i<n-1; i++)
        update(i, weight[i]);
    for (int i=1; i<=q; i++)
    {
        int ind, w;
        cin >> ind >> w;
        ind=(ind+ans)%(n-1);
        w=(w+ans)%r;
        update(ind, w-weight[ind]);
        weight[ind]=w;
        cout << -*ss.begin() << '\n';
        ans=-*ss.begin();
    }
}

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