oj.uz

Submission #447077

# Submission time Handle Problem Language Result Execution time Memory
447077 2021-07-24T11:59:36 Z yungyao Dynamic Diameter (CEOI19_diameter) C++17
31 / 100
 396 ms 42412 KB 
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;

    EDGE(int u,int v,LL w):u(u), v(v), w(w){}
    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;
    LL 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 13 ms 2764 KB Output is correct
5 Correct 98 ms 2996 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2764 KB Output is correct
8 Correct 2 ms 2764 KB Output is correct
9 Correct 3 ms 2892 KB Output is correct
10 Correct 12 ms 2960 KB Output is correct
11 Correct 53 ms 3232 KB Output is correct
12 Correct 6 ms 4556 KB Output is correct
13 Correct 7 ms 4556 KB Output is correct
14 Correct 8 ms 4556 KB Output is correct
15 Correct 20 ms 4720 KB Output is correct
16 Correct 71 ms 5028 KB Output is correct
17 Correct 137 ms 41756 KB Output is correct
18 Correct 143 ms 41736 KB Output is correct
19 Correct 187 ms 41776 KB Output is correct
20 Correct 177 ms 41924 KB Output is correct
21 Correct 396 ms 42412 KB Output is correct

Subtask #4
0 / 18.0

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

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 15580 KB Output is correct
2 Correct 186 ms 15632 KB Output is correct
3 Correct 235 ms 16960 KB Output is correct
4 Correct 264 ms 20016 KB Output is correct
5 Correct 197 ms 22220 KB Output is correct
6 Correct 227 ms 33492 KB Output is correct
7 Correct 218 ms 22144 KB Output is correct
8 Correct 229 ms 22180 KB Output is correct
9 Correct 198 ms 22064 KB Output is correct
10 Correct 212 ms 22256 KB Output is correct
11 Correct 214 ms 24384 KB Output is correct
12 Correct 226 ms 35100 KB Output is correct
13 Correct 145 ms 24388 KB Output is correct
14 Correct 178 ms 24384 KB Output is correct
15 Correct 147 ms 24352 KB Output is correct
16 Correct 195 ms 24592 KB Output is correct
17 Correct 197 ms 26504 KB Output is correct
18 Correct 224 ms 35716 KB Output is correct
19 Correct 152 ms 24364 KB Output is correct
20 Correct 134 ms 24268 KB Output is correct
21 Correct 215 ms 24388 KB Output is correct
22 Correct 170 ms 24572 KB Output is correct
23 Correct 170 ms 26408 KB Output is correct
24 Correct 170 ms 35744 KB Output is correct

Subtask #6
0 / 27.0

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