Submission #447070

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
447070	2021-07-24T11:36:33 Z	yungyao	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	5000 ms	43120 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 mt(){
        mx.resize(arr.size()*4);
        lazy.resize(arr.size()*4);
        maketree(1,1,arr.size()-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 push(int cur,int LB,int RB){
        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){
        if (l == LB and r == RB){
            lazy[cur] += val;
            push(cur,LB,RB);
            return;
        }

        push(cur,LB,RB);
        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);
        }
        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 = {};
    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;
    }
    if (adj[x].size() == 1){
        r = mkp(int(st[sti].arr.size()),int(st[sti].arr.size()));
        st[sti].arr.pb(dis);
    }

    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	2636 KB	Output is correct
3	Correct	3 ms	2636 KB	Output is correct
4	Correct	10 ms	2780 KB	Output is correct
5	Correct	43 ms	3088 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	3 ms	2892 KB	Output is correct
10	Correct	15 ms	2940 KB	Output is correct
11	Correct	53 ms	3276 KB	Output is correct
12	Correct	7 ms	4684 KB	Output is correct
13	Correct	6 ms	4684 KB	Output is correct
14	Correct	8 ms	4684 KB	Output is correct
15	Correct	20 ms	4804 KB	Output is correct
16	Correct	75 ms	5156 KB	Output is correct
17	Correct	156 ms	42580 KB	Output is correct
18	Correct	132 ms	42492 KB	Output is correct
19	Correct	139 ms	42684 KB	Output is correct
20	Correct	176 ms	42712 KB	Output is correct
21	Correct	390 ms	43120 KB	Output is correct