Submission #1308057

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308057		HoriaHaivas	Dynamic Diameter (CEOI19_diameter)	C++20	18 / 100	4700 ms	456528 KiB

diameter

#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int range_rng(int l, int r)
{
    return uniform_int_distribution<int>(l,r)(rng);
}


struct muchie
{
    int a;
    int b;
    int c;
};

struct ceva
{
    int to;
    int w;
    int id;
};

struct cmp
{
    bool operator()(ceva a, ceva b) const
    {
        return a.to<b.to;///efectiv orice
    }
};

int sz[100005];
muchie edge[100005];
set<ceva,cmp> nodes[100005];
bool blocked[100005];
map<int,int> tin[100005];
map<int,int> revstamp[100005];
map<int,int> tout[100005];
int compsize[100005];
int pathsum[100005];
int res[100005];
vector<pair<int,int>> subarbs[100005];
vector<int> centroids[100005];///in ce centroizi e muchia
multiset<int> rez;
multiset<int> altsetnushdeceamatatea[100005];
int timer;


struct Node
{
    int mxval;
    int lazy;
};

class AINT
{
public:
    int boss;
    vector<Node> aint;

    void init(int sz)
    {
        aint.resize(sz*4+5);
    }

    void build(int l, int r, int val)
    {
        if (l==r)
        {
            aint[val].mxval=pathsum[revstamp[boss][l]];
            aint[val].lazy=0;
            return;
        }
        int mid;
        mid=(l+r)/2;
        build(l,mid,val*2);
        build(mid+1,r,val*2+1);
        aint[val].mxval=max(aint[val*2].mxval,aint[val*2+1].mxval);
        aint[val].lazy=0;
    }

    void prop(int val, int l, int r)
    {
        if (aint[val].lazy==0)
            return;
        aint[val].mxval+=aint[val].lazy;
        if (l!=r)
        {
            aint[val*2].lazy+=aint[val].lazy;
            aint[val*2+1].lazy+=aint[val].lazy;
        }
        aint[val].lazy=0;
        return;
    }

    void lazy_update(int l, int r, int val, int qa, int qb, int x)
    {
        prop(val,l,r);
        if (qa<=l && r<=qb)
        {
            aint[val].lazy+=x;
            return;
        }
        int mid;
        mid=(l+r)/2;
        if (qa<=mid)
            lazy_update(l,mid,val*2,qa,qb,x);
        if (qb>mid)
            lazy_update(mid+1,r,val*2+1,qa,qb,x);
        prop(val*2,l,mid);
        prop(val*2+1,mid+1,r);
        aint[val].mxval=max(aint[val*2].mxval,aint[val*2+1].mxval);
    }

    int query(int l, int r, int val, int qa, int qb)
    {
        prop(val,l,r);
        if (qa<=l && r<=qb)
        {
            return aint[val].mxval;
        }
        int mid,ans;
        ans=-1e18;
        mid=(l+r)/2;
        if (qa<=mid)
            ans=max(ans,query(l,mid,val*2,qa,qb));
        if (qb>mid)
            ans=max(ans,query(mid+1,r,val*2+1,qa,qb));
        return ans;
    }

} aint[100005];

void update(int centroid, int node, int x)
{
    if (subarbs[centroid].size()==0)
        return;
    int r,pas,maxie;
    r=0;
    pas=(1<<16);
    while (pas)
    {
        if (r+pas<subarbs[centroid].size() && subarbs[centroid][r+pas].first<=tin[centroid][node])
            r+=pas;
        pas=pas/2;
    }
    maxie=aint[centroid].query(1,compsize[centroid],1,subarbs[centroid][r].first,subarbs[centroid][r].second);
    altsetnushdeceamatatea[centroid].erase(altsetnushdeceamatatea[centroid].find(maxie));
    aint[centroid].lazy_update(1,compsize[centroid],1,tin[centroid][node],tout[centroid][node],x);
    maxie=aint[centroid].query(1,compsize[centroid],1,subarbs[centroid][r].first,subarbs[centroid][r].second);
    altsetnushdeceamatatea[centroid].insert(maxie);
    res[centroid]=*(prev(altsetnushdeceamatatea[centroid].end()))+*(prev(prev(altsetnushdeceamatatea[centroid].end())));
}

void recalc(int node, int parent)
{
    sz[node]=1;
    for (auto x : nodes[node])
    {
        if (x.to!=parent && !blocked[x.to])
        {
            recalc(x.to,node);
            sz[node]+=sz[x.to];
        }
    }
}

int find_centroid(int node, int parent, int en)
{
    for (auto x : nodes[node])
    {
        if (x.to!=parent && !blocked[x.to] && sz[x.to]>en/2)
            return find_centroid(x.to,node,en);
    }
    return node;
}

void dfs(int node, int parent, int centroid)
{
    timer++;
    tin[centroid][node]=timer;
    revstamp[centroid][timer]=node;
    for (auto x : nodes[node])
    {
        if (x.to!=parent && !blocked[x.to])
        {
            pathsum[x.to]=pathsum[node]+x.w;
            centroids[x.id].push_back(centroid);
            dfs(x.to,node,centroid);
        }
    }
    tout[centroid][node]=timer;
}

void decomp(int node, int parent)
{
    int centroid;
    recalc(node,-1);
    centroid=find_centroid(node,-1,sz[node]);
    compsize[centroid]=sz[node];
    timer=0;
    pathsum[centroid]=0;
    dfs(centroid,-1,centroid);
    aint[centroid].boss=centroid;
    aint[centroid].init(sz[node]);
    aint[centroid].build(1,sz[node],1);
    blocked[centroid]=1;
    for (auto x : nodes[centroid])
    {
        if (x.to!=parent && !blocked[x.to])
        {
            subarbs[centroid].push_back({tin[centroid][x.to],tout[centroid][x.to]});
            decomp(x.to,centroid);
        }
    }
    sort(subarbs[centroid].begin(),subarbs[centroid].end());
}

signed main()
{
    /*
    ifstream fin("arbore.in");
    ofstream fout("arbore.out");
    */
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,q,w,i,j,a,b,c,d,e,last,parent,child,delta,maxie;
    cin >> n >> q >> w;
    for (i=1; i<=n-1; i++)
    {
        cin >> a >> b >> c;
        nodes[a].insert({b,c,i});
        nodes[b].insert({a,c,i});
        edge[i]= {a,b,c};
    }
    pathsum[1]=0;
    decomp(1,-1);
    for (i=1; i<=n; i++)
    {
        for (auto x : subarbs[i])
        {
            maxie=aint[i].query(1,compsize[i],1,x.first,x.second);
            altsetnushdeceamatatea[i].insert(maxie);
        }
        if (!altsetnushdeceamatatea[i].empty())
        {
            res[i]=*(prev(altsetnushdeceamatatea[i].end()))+*prev((prev(altsetnushdeceamatatea[i].end())));
            rez.insert(res[i]);
        }
    }
    last=0;
    for (i=1; i<=q; i++)
    {
        cin >> d >> e;
        d=(d+last)%(n-1);
        d++;
        e=(e+last)%w;
        a=edge[d].a;
        b=edge[d].b;
        for (auto x : centroids[d])
        {
            ///1. elimina rez centroizilor
            ///2. treci prin centroizi, updateaza subarborii
            ///3. treci prin centroizi din nou si vezi care sunt cele 2 frunze babane
            rez.erase(rez.find(res[x]));
            if (tin[x][a]<=tin[x][b] && tout[x][b]<=tout[x][a])
            {
                child=b;
                parent=a;
            }
            else
            {
                child=a;
                parent=b;
            }
            delta=e-edge[d].c;
            update(x,child,delta);
            rez.insert(res[x]);
        }
        cout << *(prev(rez.end())) << "\n";
        last=*(prev(rez.end()));
        edge[d].c=e;
    }
    return 0;
}

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