Submission #1246361

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246361		KindaGoodGames	Dynamic Diameter (CEOI19_diameter)	C++20	0 / 100	119 ms	22088 KiB

diameter

#pragma GCC optimize("O3, unroll-loops,Ofast")
#include<bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int,int>
#define tiii tuple<int,int,int>

int INF = numeric_limits<int>::max()/4;

struct Value{
    int ma = -INF;
    int ma2 = -INF;

    Value(){}
    Value(int a){
        ma = a; 
    }
    Value(int a, int b){
        ma = a;
        ma2 = b;
    }

    void add(int v){
        ma += v;
        ma2 += v;
    }
};

Value comb(Value a, Value b){
    vector<int> r = {a.ma,a.ma2,b.ma,b.ma2};
    sort(r.rbegin(),r.rend());
    return Value(r[0],r[1]);
}
struct SegmentTree{
    vector<Value> S;
    vector<int> lazy;
    int len = 1;

    SegmentTree(int n){
        while(len < n){
            len <<= 1;
        }

        S.resize(2*len); 
        lazy.resize(2*len); 
    }

    void upd(int i, int v){
        i += len;
        
        S[i] = Value(v);

        for(i /= 2; i > 0; i /= 2){
            S[i] = comb(S[i*2], S[i*2+1]);
        }
    }

    void apply1(int i, int v){
        S[i].add(v);
        lazy[i] += v;
    }

    void push(int i){
        apply1(i*2+1, lazy[i]);
        apply1(i*2, lazy[i]);

        lazy[i] = 0;
    }


    Value query(int ql, int qr, int l = 0, int r = -2, int i = 1){
        if(r == -2) r = len;

        if(ql <= l && r <= qr) {
            return S[i];
        }
        if(r <= ql || qr <= l) {
            return Value();
        }

        int mid = (l+r)/2;

        push(i);
        Value a = query(ql,qr,l,mid,i*2);
        Value b=  query(ql,qr,mid,r,i*2+1);
        return comb(a,b);
    }

    
    void apply(int ql, int qr, int v, int l = 0, int r = -2, int i = 1){
        if(r == -2) r = len;

        if(ql <= l && r <= qr) {
            apply1(i,v);
            return;
        }
        if(r <= ql || qr <= l) return;

        int mid = (l+r)/2;

        push(i);
        apply(ql,qr,v,l,mid,i*2);apply(ql,qr,v,mid,r,i*2+1);
        S[i] = comb(S[i*2], S[i*2+1]);
    }
};

vector<int> val, cost, ftree;
vector<int> par, sz, depth;
vector<int> start, stop;
vector<vector<pii>> adj;
int timer = 0;

void DFS(int v, int p, int d = 0, int len = 0, int f = -1){
    start[v] = timer++;

    depth[v] = d;
    sz[v] = 1;
    par[v] = p;

    int h = -1;
    int s = -1;
    for(auto u : adj[v]){
        if(u.first == p) continue;
        val[u.first] = len+u.second;
        cost[u.first] = u.second;
        
        int nf = -1;
        if(f == -1){
            nf = u.second;
        }
        DFS(u.first,v, d+1, len+u.second, nf);
        
        sz[v] += sz[u.first]; 
    } 

    stop[v] = timer;
} 

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

    vector<tiii> edges(n-1);
    adj.resize(n);
    val.resize(n);
    par = sz = val = depth = cost=start=stop= vector<int>(n,-1);

    for(int i = 0; i < n-1; i++){
        int a,b,c;
        cin >> a >> b >> c;
        a--;b--;
        edges[i] = {a,b,c};
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }

    DFS(0,0);  
    val[0] = 0;
    cost[0] = 0;

    SegmentTree seg(n);

    for(int i = 0; i < n; i++){
        seg.upd(start[i],val[i]);
    }
    
    int last = 0;
    SegmentTree seg2(adj[0].size());
    
    for(int i = 0; i < adj[0].size(); i++){ 
        auto u = adj[0][i];
        Value v = seg.query(start[u.first],stop[u.first]);
        seg2.upd(i,v.ma); 
    }
    while(q--){
        int d,e;
        cin >> d >> e;
    
        int edge = (last+d) % (n-1);
        int weight = (e+last)%w;

        int a,b,c;
        tie(a,b,c) = edges[edge];
        if(depth[a] < depth[b]) swap(a,b);
        int diff = weight-c;

        seg.apply(start[a], stop[a], diff);

        edges[edge] = {a,b,weight};
        cost[a] = weight;

        auto u = adj[0][ftree[a]];
        seg2.upd(ftree[a], seg.query(start[u.first],stop[u.first]).ma);

        int ma = 0;
        for(int i = 0; i < 1; i++){
            Value res = Value();
            
            
            int rem = seg.query(start[i], start[i]+1).ma;

            int pv = max((res.ma+res.ma2) - (2*rem),res.ma - rem);
            if(pv > ma){
                ma = max({ma, pv});
            }
        }

        cout << ma << "\n";
        last = ma;
    }
}

Compilation message (stderr)

diameter.cpp:1:46: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
    1 | #pragma GCC optimize("O3, unroll-loops,Ofast")
      |                                              ^
diameter.cpp:15:11: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   15 |     Value(){}
      |           ^
diameter.cpp:16:16: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   16 |     Value(int a){
      |                ^
diameter.cpp:19:23: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   19 |     Value(int a, int b){
      |                       ^
diameter.cpp:24:19: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   24 |     void add(int v){
      |                   ^
diameter.cpp:30:28: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   30 | Value comb(Value a, Value b){
      |                            ^
diameter.cpp:40:22: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   40 |     SegmentTree(int n){
      |                      ^
diameter.cpp:49:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   49 |     void upd(int i, int v){
      |                          ^
diameter.cpp:59:29: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   59 |     void apply1(int i, int v){
      |                             ^
diameter.cpp:64:20: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   64 |     void push(int i){
      |                    ^
diameter.cpp:72:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   72 |     Value query(int ql, int qr, int l = 0, int r = -2, int i = 1){
      |                                                                 ^
diameter.cpp:91:71: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   91 |     void apply(int ql, int qr, int v, int l = 0, int r = -2, int i = 1){
      |                                                                       ^
diameter.cpp:114:58: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
  114 | void DFS(int v, int p, int d = 0, int len = 0, int f = -1){
      |                                                          ^
diameter.cpp:140:14: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
  140 | int32_t main(){
      |              ^

• Subtask 1: 0 / 11
• Subtask 2: 0 / 13
• Subtask 3: 0 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 27