Submission #259307

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
259307	2020-08-07T14:21:44 Z	MarcoMeijer	Dynamic Diameter (CEOI19_diameter)	C++14	7 / 100	2371 ms	120880 KB

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 apply(vll& S, vll& L, int p, ll v) {
    S[p] += v;
    if(p<L.sz) L[p] += v;
}
void build(vll& S, vll& L, int p) {
    while(p>1) p>>=1, S[p]=max(S[p<<1],S[p<<1|1])+L[p];
}
void push(vll& S, vll& L, int p) {
    int h = sizeof(int)*8 - __builtin_clz((int)L.sz);
    REV(s,1,h+1) {
        int i = p>>s;
        if(L[i]!=0) {
            apply(S,L,i<<1,L[i]);
            apply(S,L,i<<1|1,L[i]);
            L[i]=0;
        }
    }
}
void addSeg(vll& S, vll& L, int l, int r, ll v) {
    l+=L.sz, r+=L.sz+1;
    int l0=l, r0=r;
    for(; l<r; l>>=1, r>>=1) {
        if(l&1) apply(S,L,l++,v);
        if(r&1) apply(S,L,--r,v);
    }
    build(S,L,l0);
    build(S,L,r0-1);
}
ll getSeg(vll& S, vll& L, int l, int r) {
    l+=L.sz, r+=L.sz+1;
    push(S,L,l);
    push(S,L,r-1);
    ll res=-1e18;
    for(; l<r; l>>=1, r>>=1) {
        if(l&1) res = max(res, S[l++]);
        if(r&1) res = max(res, S[--r]);
    }
    return res;
}
void setSeg(vll& S, vll& L, int p, ll v) {
    p+=L.sz;
    build(S,L,p);
    for (S[p] = v; p>1; p>>=1) S[p>>1] = S[p] + S[p^1];
}

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]*2, 0);
    LAZY[u].assign(cdN[u], 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)*2);
    LAZYT.resize(n+1);
    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);
    }
}

Compilation message

diameter.cpp: In function 'void apply(vll&, vll&, int, ll)':
diameter.cpp:80:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(p<L.sz) L[p] += v;
         ^

Subtask #1
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	28 ms	47360 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	28 ms	47360 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	47352 KB	Output is correct
2	Correct	29 ms	47360 KB	Output is correct
3	Correct	30 ms	47360 KB	Output is correct
4	Correct	44 ms	47480 KB	Output is correct
5	Correct	92 ms	47736 KB	Output is correct
6	Correct	29 ms	47360 KB	Output is correct
7	Correct	29 ms	47480 KB	Output is correct
8	Correct	29 ms	47488 KB	Output is correct
9	Correct	30 ms	47608 KB	Output is correct
10	Correct	47 ms	47736 KB	Output is correct
11	Correct	116 ms	48120 KB	Output is correct
12	Correct	37 ms	49144 KB	Output is correct
13	Correct	38 ms	49200 KB	Output is correct
14	Correct	38 ms	49144 KB	Output is correct
15	Correct	56 ms	49272 KB	Output is correct
16	Correct	141 ms	49784 KB	Output is correct
17	Correct	219 ms	81132 KB	Output is correct
18	Correct	223 ms	81260 KB	Output is correct
19	Correct	226 ms	81260 KB	Output is correct
20	Correct	247 ms	81260 KB	Output is correct
21	Correct	412 ms	82156 KB	Output is correct