Submission #1155141

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155141		alecurse	Dynamic Diameter (CEOI19_diameter)	C++20	100 / 100	3378 ms	298604 KiB

diameter

#include <bits/stdc++.h>
#define ll long long int
#define mp make_pair
using namespace std;
ll N, W, Q;    
vector<vector<pair<ll,ll> > > adj;
ll root = -1;
ll loggi = 30;
struct Node {
    ll val=0;
    ll lazy=0;
};

vector<ll> subtreesize;
vector<vector<ll> > radj;
vector<vector<ll> > whereto;
vector<vector<ll> > wheretocentr;
vector<bool> taken;
multiset<ll> totalmax;
vector<vector<ll> > treetravs;
vector<vector<Node> > segs;
vector<vector<ll> > fapps,lapps;
vector<multiset<ll> > sets;

ll getmaxvalnode(multiset<ll> &st) {
    if(st.size()==0)
        return 0;
    if(st.size()==1) {
        return *st.begin();
    }
    auto it = st.end();
    ll res=0;
    it=prev(it,1);
    res+=*it;
    it=prev(it,1);
    res+=*it;
    return res;
}

ll getsubtreesize(ll x, ll parent) {
    subtreesize[x]=1;
    for(auto b : adj[x]) {
        if(b.first==parent||taken[b.first])
            continue;
        subtreesize[x]+=getsubtreesize(b.first,x);
    }
    return subtreesize[x];
}

ll get_centroid(ll node, ll lastsizee, ll parent) {
    for(auto el :adj[node]) {
        if(el.first==parent||taken[el.first])   
            continue;
        if(subtreesize[el.first]*2>lastsizee) {
            return get_centroid(el.first,lastsizee,node);
        }
    }
    return node;
}

ll currentindex=0;

void dfs(ll x, ll superx, ll parent, ll level, ll indexwhere, ll indexwherecentr, ll valuesf) {
    whereto[level][x]=indexwhere;
    if(indexwherecentr!=-1) {
        wheretocentr[level][x]=indexwherecentr;

    }
    treetravs[superx].push_back(valuesf);
    fapps[level][x]=currentindex;
    currentindex++;
    for(auto el : adj[x]) {
        ll b = el.first, w=el.second;
        if(b==parent||taken[b])
            continue;
        dfs(b,superx,x,level,indexwhere,indexwherecentr == -1 ? b : indexwherecentr,valuesf+w);
    }
    treetravs[superx].push_back(valuesf);
    lapps[level][x]=currentindex;
    currentindex++;

}

void build(ll k, ll x, ll y, ll l, ll r, vector<Node > &seg, vector<ll> &vals) {
    if(y-x<=1) {
        ll threals = seg.size()/2;
        if(k-threals<vals.size()) {
            seg[k].val=vals[k-threals];
        }
        return;
    }
    ll d = (x+y)/2;
    build(k*2,x,d,l,r,seg,vals);
    build(k*2+1,d,y,l,r,seg,vals);
    seg[k].val=max(seg[k*2].val,seg[k*2+1].val);
}

void checklazy(ll k, ll x, ll y, vector<Node > &seg) {
    ll threals = seg.size()/2;
    if(k>=threals)
        return;
    if(seg[k].lazy==0)
        return;
    ll lazy = seg[k].lazy;
    seg[k].lazy=0;
    seg[k*2].val+=lazy;
    seg[k*2+1].val+=lazy;
    seg[k*2].lazy+=lazy;
    seg[k*2+1].lazy+=lazy;
    
}

ll getmax(ll k, ll x, ll y, ll l, ll r, vector<Node > &seg) {
    checklazy(k,x,y,seg);
    if(y<=l||x>=r)
        return 0;
    if(x>=l&&y<=r) {
        return seg[k].val;
    }
    ll d = (x+y)/2;
    return max(getmax(k*2,x,d,l,r,seg),getmax(k*2+1,d,y,l,r,seg));
}
void update(ll k, ll x, ll y, ll l, ll r, vector<Node > &seg,ll nval) {
    checklazy(k,x,y,seg);
     if(y<=l||x>=r)
        return;
    if(x>=l&&y<=r) {
        seg[k].val+=nval;
        seg[k].lazy=nval;
        return;
    }
    ll d = (x+y)/2;
    update(k*2,x,d,l,r,seg,nval);
    update(k*2+1,d,y,l,r,seg,nval);
    seg[k].val=max(seg[k*2].val,seg[k*2+1].val);
}
void processanodo(ll nodo, ll level) {
    currentindex=0;
    dfs(nodo,nodo,-1,level,nodo,-1,0);
    ll reals=1;
    taken[nodo]=true;
    while(reals<treetravs[nodo].size())
        reals*=2;
    segs[nodo].resize(reals*2);
    build(1,0,reals,0,reals,segs[nodo],treetravs[nodo]);
    for(auto el : adj[nodo]) {
        ll b = el.first;
        if(taken[b])
            continue;
        ll thval = getmax(1,0,reals,fapps[level][b],lapps[level][b]+1,segs[nodo]);
        sets[nodo].insert(thval);
    
    }
    totalmax.insert(getmaxvalnode(sets[nodo]));
}   

void bfs() {
    queue<pair<ll,ll> > q;
    q.push(mp(root,0));
    while(!q.empty()) {
        ll x = q.front().first, level = q.front().second;
        q.pop();
        processanodo(x,level);
        for(auto b : radj[x]) {
            q.push(mp(b,level+1));
        }
    }
}
void modifica(ll nodoa, ll nodob, ll valore, ll nodo, ll level) {
    ll nodepar = 0;
    if(nodoa==nodo) {
        nodepar=nodob;
    } else if(nodob==nodo) {
        nodepar=nodoa;
    } else {
        nodepar=wheretocentr[level][nodoa];
    }
    if(radj[nodo].size()==0)
        return;
    // totalmax.erase(totalmax.find(getmaxvalnode(sets[nodo])));
    auto it = totalmax.find(getmaxvalnode(sets[nodo]));
    totalmax.erase(it);
    // cout<<fapps[level][nodepar]<<" "<<lapps[level][nodepar]<<" "<<segs[nodo].size()/2<<"\n";
   
    ll thval = getmax(1,0,segs[nodo].size()/2,fapps[level][nodepar],lapps[level][nodepar]+1,segs[nodo]);
     it = sets[nodo].find(thval);
    if(it==sets[nodo].end()) {
        //   cout<<nodo<<" "<<nodepar<<" "<<nodoa<<" "<<thval<<"\n";
    }
    assert(it!=sets[nodo].end());
    sets[nodo].erase(it);
    int nodotouse = nodoa;
    if(fapps[level][nodob]>fapps[level][nodoa]) {
        nodotouse=nodob;
    }
    update(1,0,segs[nodo].size()/2,fapps[level][nodotouse],lapps[level][nodotouse]+1,segs[nodo],valore);
    thval = getmax(1,0,segs[nodo].size()/2,fapps[level][nodepar],lapps[level][nodepar]+1,segs[nodo]);
    sets[nodo].insert(thval);
    totalmax.insert(getmaxvalnode(sets[nodo]));
    ll nextnode = whereto[level+1][nodoa];
    
    
    if(nextnode==-1)
        return;
    if(whereto[level+1][nodob]==-1)
        return;
    modifica(nodoa,nodob,valore,nextnode,level+1);
}
void buildcentroid(ll node, ll last) {
    ll centroid = get_centroid(node,getsubtreesize(node,-1),-1);
    if(last==-1) {
        root = centroid;
    } else {
        radj[last].push_back(centroid);
    }
    taken[centroid]=true;
    for(auto el : adj[centroid]) {
        ll b = el.first;
        if(taken[b])
            continue;
        buildcentroid(b,centroid);
        
    }
}



int main() {
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    cin>>N>>Q>>W;
    adj.resize(N);
    vector<pair<pair<ll,ll>,ll> > edges;
    for(ll i=0;i<N-1;i++) {
        ll a,b,c;
        cin>>a>>b>>c;
        a--;
        b--;
        edges.push_back(mp(mp(a,b),c));
        adj[a].push_back(mp(b,c));
        adj[b].push_back(mp(a,c));
    }
    radj.resize(N);
    whereto.assign(loggi,vector<ll> (N,-1));
    wheretocentr.resize(loggi, vector<ll> (N));
    fapps.resize(loggi, vector<ll> (N));
    lapps.resize(loggi, vector<ll> (N));
    segs.resize(N);
    sets.resize(N);
    treetravs.resize(N);
    subtreesize.resize(N);
    taken.resize(N);
    buildcentroid(0,-1);
    taken.clear();
    taken.resize(N);
    bfs();
    ll last=0;
    for(ll i=0;i<Q;i++) {
        ll d, e;
        cin>>d>>e;
       
        d=(d+last)%(N-1);
        e=(e+last)%W;
        ll nodea = edges[d].first.first, nodeb=edges[d].first.second;
        modifica(nodea,nodeb,e-edges[d].second,root,0);
        edges[d].second=e;
        auto it = totalmax.end();
        it=prev(it,1);
        last=*it;
        cout<<last<<"\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