답안 #259305

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
259305	2020-08-07T14:20:40 Z	MarcoMeijer	Dynamic Diameter (CEOI19_diameter)	C++14	7 / 100	2280 ms	124928 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;
    push(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

#	결과	실행 시간	메모리	Grader output
1	Incorrect	28 ms	47352 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	28 ms	47352 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	36 ms	47352 KB	Output is correct
2	Correct	28 ms	47276 KB	Output is correct
3	Correct	36 ms	47352 KB	Output is correct
4	Correct	43 ms	47608 KB	Output is correct
5	Correct	100 ms	48504 KB	Output is correct
6	Correct	29 ms	47352 KB	Output is correct
7	Correct	32 ms	47616 KB	Output is correct
8	Correct	31 ms	47480 KB	Output is correct
9	Correct	41 ms	47608 KB	Output is correct
10	Correct	49 ms	47864 KB	Output is correct
11	Correct	118 ms	48888 KB	Output is correct
12	Correct	36 ms	49400 KB	Output is correct
13	Correct	37 ms	49280 KB	Output is correct
14	Correct	38 ms	49272 KB	Output is correct
15	Correct	57 ms	49528 KB	Output is correct
16	Correct	136 ms	50808 KB	Output is correct
17	Correct	213 ms	82412 KB	Output is correct
18	Correct	212 ms	82540 KB	Output is correct
19	Correct	220 ms	82412 KB	Output is correct
20	Correct	251 ms	82796 KB	Output is correct
21	Correct	392 ms	84336 KB	Output is correct