Submission #258952

#	Time	Username	Problem	Language	Result	Execution time	Memory
258952		MarcoMeijer	Dynamic Diameter (CEOI19_diameter)	C++14	49 / 100	5103 ms	195344 KiB

diameter

#include <bits/stdc++.h>
using namespace std;

// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e9
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
#define sz size()

// input
template<class T> void IN(T& x) {cin >> x;}
template<class H, class... T> void IN(H& h, T&... t) {IN(h); IN(t...); }

// output
template<class T1, class T2> void OUT(const pair<T1,T2>& x);
template<class T> void OUT(const T& x) {cout << x;}
template<class H, class... T> void OUT(const H& h, const T&... t) {OUT(h); OUT(t...); }
template<class T1, class T2> void OUT(const pair<T1,T2>& x) {OUT(x.fi," ",x.se);}
template<class... T> void OUTL(const T&... t) {OUT(t..., "\n"); }

//===================//
//  Added libraries  //
//===================//

//===================//
//end added libraries//
//===================//

void program();
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    program();
}


//===================//
//   begin program   //
//===================//

const int MX = 2e5;
int n, q;
ll w, last=0;
map<int,int> edgeN[MX];
set<int> adj[MX];
int a[MX], b[MX]; ll c[MX];
int SZ[MX];

vll SEG[MX], LAZY[MX];
int cdN[MX];
viii infl[MX];
int bg[MX], ed[MX], curbg, curSeg;
vii segAreas[MX];
map<ll,int> SEGCNT[MX];
vll SEGT, LAZYT;

void setSeg(vll& SEG, vll& LAZY, int i, ll v, ll lazy=0, int p=0, int l=0, int r=-1) {
    if(r == -1) r = SEG.sz/4-1;
    SEG [p] += lazy;
    LAZY[p] += lazy;
    if(i < l || i > r) return;
    if(l == r) {
        SEG [p] = v;
        return;
    }
    int m=(l+r)/2;
    setSeg(SEG,LAZY,i,v,LAZY[p],p*2+1,l,m);
    setSeg(SEG,LAZY,i,v,LAZY[p],p*2+2,m+1,r);
    SEG [p] = max(SEG[p*2+1], SEG[p*2+2]);
    LAZY[p] = 0;
}
void addSeg(vll& SEG, vll& LAZY, int i, int j, ll v, ll lazy=0, int p=0, int l=0, int r=-1) {
    if(r == -1) r = SEG.sz/4-1;
    SEG [p] += lazy;
    LAZY[p] += lazy;
    if(j < l || i > r) return;
    if(i <= l && j >= r) {
        SEG [p] += v;
        LAZY[p] += v;
        return;
    }
    int m=(l+r)/2;
    addSeg(SEG,LAZY,i,j,v,LAZY[p],p*2+1,l,m);
    addSeg(SEG,LAZY,i,j,v,LAZY[p],p*2+2,m+1,r);
    SEG [p] = max(SEG[p*2+1], SEG[p*2+2]);
    LAZY[p] = 0;
}
ll getSeg(vll& SEG, vll& LAZY, int i, int j, ll lazy=0, int p=0, int l=0, int r=-1) {
    if(r == -1) r = SEG.sz/4-1;
    SEG [p] += lazy;
    LAZY[p] += lazy;
    if(j < l || i > r) return -1e18;
    if(i <= l && j >= r) return SEG[p];
    int m=(l+r)/2;
    ll a = getSeg(SEG,LAZY,i,j,LAZY[p],p*2+1,l,m);
    ll b = getSeg(SEG,LAZY,i,j,LAZY[p],p*2+2,m+1,r);
    LAZY[p] = 0;
    return max(a,b);    
}

void dfsSZ(int u, int p=-1) {
    SZ[u] = 1;
    FOR(v,adj[u]) if(v!=p) dfsSZ(v,u), SZ[u]+=SZ[v];
}
int dfsCent(int u, int p, int tot) {
    FOR(v,adj[u]) if(v!=p && SZ[v] > tot/2) return dfsCent(v,u,tot);
    return u;
}
int findCentroid(int u) {
    dfsSZ(u);
    return dfsCent(u,-1,SZ[u]);
}

void dfsBG(int u, int p=-1) {
    bg[u] = curbg++;
    FOR(v,adj[u]) if(v!=p) {
        dfsBG(v,u);
        int e = edgeN[u][v];
        infl[e].pb({curSeg,bg[v],ed[v]});
        addSeg(SEG[curSeg], LAZY[curSeg], bg[v], ed[v], c[e]);
        if(u == curSeg) {
            segAreas[u].pb({bg[v],ed[v]});
        }
    }
    ed[u] = curbg-1;
}
void updateSeg(int u) {
    ll res=0, used=0;
    auto it = SEGCNT[u].end();
    while(used<2) {
        if(it == SEGCNT[u].begin()) break;
        it--;
        if(used == 1 || it->se == 1) {
            res += it->fi;
        } else {
            res += it->fi*2ll;
        }
        used += it->se;
    }
    setSeg(SEGT,LAZYT,u,res);
}
void createSeg(int u) {
    dfsSZ(u);
    cdN[u] = SZ[u];
    SEG [u].assign(cdN[u]*4, 0);
    LAZY[u].assign(cdN[u]*4, 0);

    curbg=0;
    curSeg=u;
    dfsBG(u);
    FOR(p,segAreas[u]) SEGCNT[u][getSeg(SEG[u],LAZY[u],p.fi,p.se)]++;
    updateSeg(u);
}
void centDe(int u) {
    int cent = findCentroid(u);
    createSeg(cent);

    for(int v:adj[cent]) {
        adj[v].erase(cent);
        centDe(v);
    }
    adj[cent].clear();
}

void program() {
    IN(n,q,w);
    RE1(i,n-1) {
        IN(a[i],b[i],c[i]);
        adj[a[i]].insert(b[i]);
        adj[b[i]].insert(a[i]);
        edgeN[a[i]][b[i]] = i;
        edgeN[b[i]][a[i]] = i;
    }
    SEGT.resize((n+1)*4);
    LAZYT.resize((n+1)*4);
    centDe(1);

    RE(queryNumber,q) {
        ll d, e; IN(d,e);
        d = (d+last)%(n-1); d++;
        e = (e+last)%w;
        FOR(p,infl[d]) {
            int bgs, eds;
            tie(curSeg, bgs, eds) = p;
            ii p2 = *(--lower_bound(all(segAreas[curSeg]), ii{bgs,INF}));
            ll gsres = getSeg(SEG[curSeg],LAZY[curSeg],p2.fi,p2.se);
            if(--SEGCNT[curSeg][gsres] == 0) SEGCNT[curSeg].erase(gsres);
            addSeg(SEG[curSeg], LAZY[curSeg], bgs, eds, -c[d]);
            addSeg(SEG[curSeg], LAZY[curSeg], bgs, eds, e);
            SEGCNT[curSeg][getSeg(SEG[curSeg],LAZY[curSeg],p2.fi,p2.se)]++;
            updateSeg(curSeg);
        }
        c[d] = e;
        last = getSeg(SEGT,LAZYT,0,n);
        OUTL(last);
    }
}

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