Submission #447058

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
447058	2021-07-24T11:15:25 Z	yungyao	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	5000 ms	43156 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+10,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 (!r.F){
        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]].query(1,st[belong[m]].arr.size()-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;
}

Compilation message

diameter.cpp: In member function 'void segtree::push(int, int, int)':
diameter.cpp:70:27: warning: value computed is not used [-Wunused-value]
   70 |             lazy[cur*2+1] == lazy[cur];

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	46 ms	3064 KB	Output is correct
6	Correct	2 ms	2636 KB	Output is correct
7	Correct	3 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	16 ms	2944 KB	Output is correct
11	Correct	55 ms	3280 KB	Output is correct
12	Correct	7 ms	4696 KB	Output is correct
13	Correct	6 ms	4684 KB	Output is correct
14	Correct	8 ms	4680 KB	Output is correct
15	Correct	19 ms	4720 KB	Output is correct
16	Correct	73 ms	5088 KB	Output is correct
17	Correct	145 ms	42512 KB	Output is correct
18	Correct	138 ms	42544 KB	Output is correct
19	Correct	134 ms	42516 KB	Output is correct
20	Correct	166 ms	42704 KB	Output is correct
21	Correct	402 ms	43156 KB	Output is correct