Submission #447075

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
447075	2021-07-24T11:57:07 Z	yungyao	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	5000 ms	43184 KB

diameter

using namespace std;
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <utility>
#include <memory.h>
#include <vector>
#include <bitset>

typedef pair<int,int> pii;
typedef long long LL;

#define iter(x) x.begin(),x.end()
#define F first
#define S second
#define pb push_back
#define mkp make_pair

#include <climits>
const int maxn = 1e5+100,mod = 0;

struct EDGE{
    int u,v;
    LL w;
    int con_to(int e){
        return u == e ? v : u;
    }
    int l,r;

    EDGE(int u,int v,LL w):u(u), v(v), w(w), l(0), r(0){}
    EDGE(){}
}edge[maxn];

vector <pair<int,LL>> adj[maxn];
int father[maxn];
pii seg[maxn];
LL mx[maxn];

#define mid (LB+RB)/2

struct segtree{
    vector <LL> arr,mx,lazy;
    segtree(){
        arr.resize(1);
    }

    void maketree(int cur,int LB,int RB){
        if (LB == RB) mx[cur] = arr[LB];
        else{
            maketree(cur*2,LB,mid);
            maketree(cur*2+1,mid+1,RB);
            mx[cur] = max(mx[cur*2],mx[cur*2+1]);
        }
    }

    void mt(){
        mx.resize(arr.size()*4);
        lazy.resize(arr.size()*4);
        maketree(1,1,arr.size()-1);
    }

    void push(int cur,int LB,int RB){
        if (lazy[cur]){
            mx[cur] += lazy[cur];
            if (LB != RB){
                lazy[cur*2] += lazy[cur];
                lazy[cur*2+1] += lazy[cur];
            }
            lazy[cur] = 0;
        }
    }

    void ru(int l,int r,LL val,int cur,int LB,int RB){
        push(cur,LB,RB);
        if (l == LB and r == RB){
            lazy[cur] += val;
            push(cur,LB,RB);
            return;
        }

        if (r <= mid) ru(l,r,val,cur*2,LB,mid);
        else if (l > mid) ru(l,r,val,cur*2+1,mid+1,RB);
        else{
            ru(l,mid,val,cur*2,LB,mid);
            ru(mid+1,r,val,cur*2+1,mid+1,RB);
        }
        push(cur*2,LB,mid);
        push(cur*2+1,mid+1,RB);
        mx[cur] = max(mx[cur*2],mx[cur*2+1]);
    }

    LL rq(int l,int r,int cur,int LB,int RB){
        push(cur,LB,RB);
        if (l == LB and r == RB) return mx[cur];

        if (r <= mid) return rq(l,r,cur*2,LB,mid);
        else if (l > mid) return rq(l,r,cur*2+1,mid+1,RB);
        else return max(rq(l,mid,cur*2,LB,mid),rq(mid+1,r,cur*2+1,mid+1,RB));
    }

    void upd(int l,int r,LL val){
        ru(l,r,val,1,1,arr.size()-1);
    }
    LL query(int l,int r){
        return rq(l,r,1,1,arr.size()-1);
    }
};

vector <segtree> st;
int belong[maxn],treecnt;

pii dfs(int x,int fr,LL dis,int sti){
    father[x] = fr;
    belong[x] = sti;
    pii r = {};
    if (adj[x].size() == 1){
        r = mkp(int(st[sti].arr.size()),int(st[sti].arr.size()));
        st[sti].arr.pb(dis);
    }
    else
        for (auto [i,w]:adj[x]) if (i != fr){
            if (!r.F) r = dfs(i,x,dis + w,sti); 
            else r.S = dfs(i,x,dis + w,sti).S;
        }

    seg[x] = r;
    return r;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n,q,w;

    cin >> n >> q >> w;
    for (int i=0;i<n-1;++i){
        int u,v; LL c;

        cin >> u >> v >> c;
        edge[i] = EDGE(u,v,c);
        adj[u].pb(mkp(v,c));
        adj[v].pb(mkp(u,c));
    }

    st.resize(adj[1].size());
    multiset <LL> ms;
    for (auto [i,d]:adj[1]){
        dfs(i,1,d,treecnt);
        st[treecnt].mt();
        mx[treecnt] = st[treecnt].mx[1];
        ms.insert(mx[treecnt]);

        ++treecnt;
    }

    for (int i=0;i<n-1;++i){
        if (edge[i].u == father[edge[i].v])
            swap(edge[i].u,edge[i].v);
    }

    LL last = 0;
    while (q--){
        LL d,e;

        cin >> d >> e;
        d = (last + d) % (n-1);
        e = (last + e) % w;

        LL dif = e - edge[d].w;
        int m = edge[d].u;
        edge[d].w = e;

        ms.erase(ms.find(mx[belong[m]]));
        st[belong[m]].upd(seg[m].F,seg[m].S,dif);
        mx[belong[m]] = st[belong[m]].mx[1];
        ms.insert(mx[belong[m]]);

        last = *prev(ms.end()) + (ms.size() > 1 ? *prev(prev(ms.end())) : 0);

        cout /*<< d << ' ' << e << ' '*/ << last << '\n';
    }

    return 0;
}

Subtask #1
0 / 11.0

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

Subtask #2
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	2636 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	2 ms	2636 KB	Output is correct
2	Correct	2 ms	2584 KB	Output is correct
3	Correct	3 ms	2636 KB	Output is correct
4	Correct	10 ms	2792 KB	Output is correct
5	Correct	43 ms	3000 KB	Output is correct
6	Correct	2 ms	2636 KB	Output is correct
7	Correct	2 ms	2892 KB	Output is correct
8	Correct	2 ms	2892 KB	Output is correct
9	Correct	4 ms	2892 KB	Output is correct
10	Correct	13 ms	2928 KB	Output is correct
11	Correct	53 ms	3320 KB	Output is correct
12	Correct	7 ms	4684 KB	Output is correct
13	Correct	7 ms	4684 KB	Output is correct
14	Correct	9 ms	4724 KB	Output is correct
15	Correct	19 ms	4740 KB	Output is correct
16	Correct	72 ms	5152 KB	Output is correct
17	Correct	139 ms	42464 KB	Output is correct
18	Correct	141 ms	42560 KB	Output is correct
19	Correct	142 ms	42628 KB	Output is correct
20	Correct	174 ms	42588 KB	Output is correct
21	Correct	376 ms	43184 KB	Output is correct