Submission #770424

#	Time	Username	Problem	Language	Result	Execution time	Memory
770424		JakobZorz	Dynamic Diameter (CEOI19_diameter)	C++14	100 / 100	3903 ms	522552 KiB

diameter

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
#include <stack>
#include <limits.h>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <map>
#include <cstring>
#include <sstream>
 
#pragma GCC target("popcnt")
 
typedef long long ll;
typedef long double ld;
using namespace std;
const int MOD = 1e9+7;
typedef pair<ld,ld> point;
#define x first
#define y second

//#define SEGTREE
//#define TREE
//#define DSU
//#define MATH
 
#ifdef SEGTREE
template<class Type>
class SegmentTree {
    Type (*func)(Type a, Type b);
    vector<Type> nodes;
    vector<int> l;
    vector<int> r;
    int size_log2;
    Type neutral;
    
    void init_node(int node) {
        if(node >= (1 << size_log2))
            return;
        
        l[2 * node] = l[node];
        r[2 * node] = (l[node] + r[node]) / 2;
        init_node(2 * node);
        
        l[2 * node + 1] = (l[node] + r[node]) / 2;
        r[2 * node + 1] = r[node];
        init_node(2 * node + 1);
        
        nodes[node] = func(nodes[2 * node], nodes[2 * node + 1]);
    }
    
    void update_node(int node) {
        if(node < (1 << size_log2))
            nodes[node] = func(nodes[2 * node], nodes[2 * node + 1]);
        
        if(node != 1)
            update_node(node / 2);
    }
    
    Type get(int node, int ll_, int rr) {
        if(rr <= l[node] || ll_ >= r[node])
            return neutral;
        
        if(ll_ <= l[node] && rr >= r[node])
            return nodes[node];
        
        Type left = get(2 * node, ll_, rr);
        Type right = get(2 * node + 1, ll_, rr);
        
        return func(left, right);
    }
    
public:
    SegmentTree(Type (*func)(Type a, Type b), vector<Type> vector, Type neutral) : func(func), neutral(neutral) {
        size_log2 = 0;
        while((1 << size_log2) < vector.size())
            size_log2++;
        
        nodes.resize((1 << size_log2) * 2);
        l.resize((1 << size_log2) * 2);
        r.resize((1 << size_log2) * 2);
        
        for(int i = 0; i < vector.size(); i++)
            nodes[(1 << size_log2) + i] = vector[i];
        
        l[1] = 0;
        r[1] = 1 << size_log2;
        init_node(1);
    }
    
    void set(int idx, Type el) {
        nodes[(1 << size_log2) + idx] = el;
        update_node((1 << size_log2) + idx);
    }
    
    Type get(int l, int r) {
        return get(1, l, r);
    }
    
    Type get(int idx) {
        return nodes[(1 << size_log2) + idx];
    }
    
    Type get() {
        return nodes[1];
    }
    
    int get_first_larger_or_eq_than(int bound) {
        return get_first_larger_or_eq_than(1, bound);
    }
    
    int get_first_larger_or_eq_than(int node, int bound) {
        if(node >= (1 << size_log2)) {
            return node - (1 << size_log2);
        }
        
        if(nodes[node * 2] > bound)
            return get_first_larger_or_eq_than(node * 2, bound);
        else
            return get_first_larger_or_eq_than(node * 2 + 1, bound - nodes[node * 2]);
    }
};
 
#endif
 
#ifdef TREE
#define POW 18
 
struct Node {
    int parents[POW];
    vector<int> conns;
    int depth;
    int value;
    int subtree_depth;
    int subtree_size;
    int euler;
    int val;
    int res;
};
 
ll add(ll a, ll b) {
    return a + b;
}
 
Node nodes[200000];
int n;
 
int setup(int node, int depth, int euler, ll dist) {
    dist += nodes[node].value;
    nodes[node].depth = depth;
    nodes[node].euler = euler++;
    
    
    for(int i = 1; i < POW; i++) {
        nodes[node].parents[i] = nodes[nodes[node].parents[i - 1]].parents[i - 1];
    }
    
    int size = 1;
    
    for(int i = 0; i < nodes[node].conns.size(); i++) {
        int child = nodes[node].conns[i];
        if(child != nodes[node].parents[0]) {
            nodes[child].parents[0] = node;
            euler = setup(child, depth + 1, euler, dist);
            size += nodes[child].subtree_size;
        }
    }
    nodes[node].subtree_size = size;
    return euler;
}
 
void setup_tree(int root) {
    nodes[root].parents[0] = root;
    setup(root, 0, 0, 0);
}
 
int get_subtree_depth(int node) {
    if(nodes[node].subtree_depth)
        return nodes[node].subtree_depth;
    
    int max_depth = 1;
    for(int child : nodes[node].conns) {
        if(child == nodes[node].parents[0])
            continue;
        max_depth = max(max_depth, get_subtree_depth(child) + 1);
    }
    nodes[node].subtree_depth = max_depth;
    return max_depth;
}
 
int get_parent(int node, int depth) {
    if(depth > nodes[node].depth)
        return -1;
    
    int climber = node;
    for(int i = 0; i < POW; i++) {
        if(depth & (1 << i) && climber != -1)
            climber = nodes[climber].parents[i];
    }
    
    return climber;
}

bool is_sub(int a,int b){
    return get_parent(a,nodes[a].depth-nodes[b].depth)==b;
}
 
int lca(int a, int b) {
    if(nodes[a].depth < nodes[b].depth)
        swap(a, b);
    
    a = get_parent(a, nodes[a].depth - nodes[b].depth);
    
    if(a == b)
        return a;
    
    for(int i = POW - 1; i >= 0; i--) {
        if(nodes[a].parents[i] != nodes[b].parents[i]) {
            a = nodes[a].parents[i];
            b = nodes[b].parents[i];
        }
    }
    
    return nodes[a].parents[0];
}
 
#endif
 
#ifdef DSU
 
class Dsu {
    vector<int> arr;
    int num_sets;
    
public:
    Dsu(int size) {
        arr = vector<int>(size, -1);
        num_sets = size;
    }
    
    int merge(int a, int b) {
        a = get(a);
        b = get(b);
        
        if(a == b)
            return a;
        
        if(arr[a] > arr[b])
            swap(a, b);
        
        arr[a] += arr[b];
        arr[b] = a;
        num_sets--;
        return a;
    }
    
    int get(int a) {
        if(arr[a] < 0)
            return a;
        arr[a] = get(arr[a]);
        return get(arr[a]);
    }
    
    int get_size(int a) {
        return -arr[get(a)];
    }
    
    int get_num_sets() {
        return num_sets;
    }
};
 
#endif
 
#ifdef MATH
 
ll dpf[2000001];
ll factorial(ll n) {
    if(n == 0)
        return 1;
    
    if(dpf[n])
        return dpf[n];
    
    ll result = factorial(n - 1) * n;
    result %= MOD;
    dpf[n] = result;
    return result;
}
 
ll powm(ll base, ll exp) {
    ll result = 1;
    
    for(int i = 0; i < 64; i++) {
        if((exp >> i) % 2 == 1) {
            result *= base;
            result %= MOD;
        }
        base *= base;
        base %= MOD;
    }
    
    return result;
}
 
ll inverse(ll n) {
    return powm(n, MOD - 2);
}
 
ll dpif[2000001];
ll inverse_factorial(ll n) {
    if(dpif[n])
        return dpif[n];
    
    ll result = inverse(factorial(n));
    dpif[n] = result;
    return result;
}
 
ll choose(ll n, ll k) {
    return (((factorial(n)*inverse_factorial(n-k))%MOD)*inverse_factorial(k))%MOD;
}
 
ll gcd(ll a, ll b){
    if(a==b)
        return a;
    if(a<b)
        swap(a,b);
    if(b==0)
        return a;
    return gcd(b, a%b);
}
 
#endif

class Arr{
    vector<ll>tree;
    vector<int>l,r;
    vector<ll>lazy;
    int tree_size;
    void init_node(int node,int left,int right){
        int mid=(left+right)/2;
        l[node]=left;
        r[node]=right;
        if(node<tree_size){
            init_node(2*node,left,mid);
            init_node(2*node+1,mid,right);
            tree[node]=max(tree[2*node],tree[2*node+1]);
        }
    }
    
    void push_node(int node){
        tree[node]+=lazy[node];
        if(node<tree_size){
            lazy[2*node]+=lazy[node];
            lazy[2*node+1]+=lazy[node];
        }
        lazy[node]=0;
    }
    
    ll get_max_node(int node,int left,int right){
        push_node(node);
        if(left<=l[node]&&r[node]<=right)
            return tree[node];
        
        if(r[node]<=left||right<=l[node])
            return 0;
        
        return max(get_max_node(2*node,left,right),get_max_node(2*node+1,left,right));
    }
    
    void inc_node(int node,int left,int right,ll s){
        push_node(node);
        if(left<=l[node]&&r[node]<=right){
            lazy[node]+=s;
            push_node(node);
            return;
        }
        
        if(r[node]<=left||right<=l[node])
            return;
        
        inc_node(2*node,left,right,s);
        inc_node(2*node+1,left,right,s);
        tree[node]=max(tree[2*node],tree[2*node+1]);
    }
    
public:
    Arr(vector<ll>v){
        tree_size=1;
        while(tree_size<(int)v.size())
            tree_size*=2;
        tree.resize(2*tree_size);
        for(int i=0;i<(int)v.size();i++)
            tree[tree_size+i]=v[i];
        l.resize(2*tree_size);
        r.resize(2*tree_size);
        lazy.resize(2*tree_size);
        init_node(1,0,tree_size);
    }
    
    Arr()=default;
    
    ll get_max(int l,int r){
        return get_max_node(1,l,r);
    }
    
    void inc(int l,int r,ll c){
        inc_node(1,l,r,c);
    }
};

class Context{
    int curr=1;
    unordered_map<int,int>m;
public:
    void add(int a){
        if(m[a]==0)
            m[a]=curr++;
    }
    
    int get(int a){
        return m[a]-1;
    }
    
    bool has(int a){
        return m[a]!=0;
    }
};

class Tree{
    Context context;
    vector<ll>leaves_vec;
    Arr leaves;
    vector<int>leaves_l;
    vector<int>leaves_r;
    vector<vector<pair<int,ll>>>nodes;
    vector<int>parents;
    vector<int>parent_root;
    vector<int>parent_root_idx;
    vector<ll>parentsw;
    vector<vector<int>>children;
    multiset<ll>root_children,subtree_res;
    vector<Tree*>subtrees;
    int n,root;
    vector<int>conns1;
    vector<int>conns2;
    vector<ll>conns3;
    ll prev_res=0;
    
    void init_node(int node,int par,ll d){
        parents[node]=par;
        leaves_l[node]=10000000;
        leaves_r[node]=0;
        for(pair<int,ll> ch:nodes[node]){
            if(ch.first==par){
                parentsw[node]=ch.second;
                continue;
            }
            
            init_node(ch.first,node,d+ch.second);
            children[node].push_back(ch.first);
            leaves_l[node]=min(leaves_l[node],leaves_l[ch.first]);
            leaves_r[node]=max(leaves_r[node],leaves_r[ch.first]);
        }
        if(children[node].empty()){
            leaves_l[node]=(int)leaves_vec.size();
            leaves_r[node]=(int)leaves_vec.size()+1;
            leaves_vec.push_back(d);
        }
    }
    
    void init_node_2(int node,int par_root,int par_root_idx){
        parent_root[node]=par_root;
        parent_root_idx[node]=par_root_idx;
        for(int ch:children[node])
            init_node_2(ch,par_root,par_root_idx);
    }
    
    void get_conns(int node){
        for(int ch:children[node]){
            conns1.push_back(node);
            conns2.push_back(ch);
            conns3.push_back(parentsw[ch]);
            get_conns(ch);
        }
    }
    
    vector<vector<int>>children2;
    vector<int>subtree_size;
    void init_node_3(int node,int par){
        subtree_size[node]=1;
        for(pair<int,ll>ne:nodes[node]){
            if(ne.first==par)
                continue;
            init_node_3(ne.first,node);
            children2[node].push_back(ne.first);
            subtree_size[node]+=subtree_size[ne.first];
        }
    }
    
    int get_centroid(){
        init_node_3(0,-1);
        int curr=0;
        while(true){
            int prev=curr;
            for(int ch:children2[curr])
                if(subtree_size[ch]>=n/2){
                    curr=ch;
                    break;
                }
            if(prev==curr)
                break;
        }
        return curr;
    }
    
public:
    Tree(int n):n(n){
        if(n<=1)
            return;
        nodes.resize(n);
        parents.resize(n);
        parentsw.resize(n);
        children.resize(n);
        leaves_l.resize(n);
        leaves_r.resize(n);
        parent_root.resize(n);
        children2.resize(n);
        subtree_size.resize(n);
        parent_root_idx.resize(n);
    }
    
    void add_edge(int a,int b,ll c){
        context.add(a);
        context.add(b);
        a=context.get(a);
        b=context.get(b);
        nodes[a].emplace_back(b,c);
        nodes[b].emplace_back(a,c);
    }
    
    void init_tree(){
        if(n<=1)
            return;
        root=get_centroid();
        init_node(root,-1,0);
        leaves=Arr(leaves_vec);
        int i=0;
        for(int ch:children[root]){
            init_node_2(ch,ch,i);
            root_children.insert(leaves.get_max(leaves_l[ch],leaves_r[ch]));
            conns1.clear();
            conns2.clear();
            conns3.clear();
            get_conns(ch);
            subtrees.push_back(new Tree((int)conns1.size()+1));
            for(int i=0;i<(int)conns1.size();i++)
                subtrees.back()->add_edge(conns1[i],conns2[i],conns3[i]);
            subtrees.back()->init_tree();
            i++;
        }
        ll res=0;
        if(root_children.size()==1)
            res=*--root_children.end();
        else
            res=*--root_children.end()+*--(--root_children.end());
        
        for(Tree*tree:subtrees){
            ll res2=tree->prev_res;
            res=max(res,res2);
            subtree_res.insert(res2);
        }
        prev_res=res;
    }
    
    ll set_edge(int a,int b,ll c){
        //cout<<"set: "<<a<<" "<<b<<"\n";
        if(!context.has(a)||!context.has(b)||n<=1)
            return prev_res;
        
        a=context.get(a);
        b=context.get(b);
        
        // b is parent of a
        if(parents[a]!=b)
            swap(a,b);
        
        int root_ch=parent_root[a];
        root_children.erase(root_children.find(leaves.get_max(leaves_l[root_ch],leaves_r[root_ch])));
        
        ll diff=c-parentsw[a];
        parentsw[a]=c;
        leaves.inc(leaves_l[a],leaves_r[a],diff);
        
        root_children.insert(leaves.get_max(leaves_l[root_ch],leaves_r[root_ch]));
        
        ll res=0;
        if(root_children.size()==1)
            res=*--root_children.end();
        else
            res=*--root_children.end()+*--(--root_children.end());
        
        int subtree=parent_root_idx[a];
        
        subtree_res.erase(subtree_res.find(subtrees[subtree]->prev_res));
        subtree_res.insert(subtrees[subtree]->set_edge(a,b,c));
        res=max(res,*--subtree_res.end());
        /*for(Tree*tree:subtrees){
            ll res2=tree->set_edge(a,b,c);
            res=max(res,res2);
        }*/
        prev_res=res;
        //cout<<"res: "<<res<<"\n";
        return res;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);
    
    //freopen("speeding.in","r",stdin);
    //freopen("speeding.out","w",stdout);
    
    ll n,q,w;
    vector<pair<int,int>> edges;
    cin>>n>>q>>w;
    edges.resize(n-1);
    Tree tree((int)n);
    
    for(int i=0;i<n-1;i++){
        int a,b;
        ll c;
        cin>>a>>b>>c;
        a--;b--;
        edges[i]={a,b};
        tree.add_edge(a,b,c);
    }
    
    tree.init_tree();
    
    ll last=0;
    while(q--){
        ll d,e;
        cin>>d>>e;
        d=(d+last)%(n-1);
        e=(e+last)%w;
        last=tree.set_edge(edges[d].first,edges[d].second,e);
        cout<<last<<"\n";
    }
    
    return 0;
}

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