Submission #201169

#	Time	Username	Problem	Language	Result	Execution time	Memory
201169		georgerapeanu	Dynamic Diameter (CEOI19_diameter)	C++11	7 / 100	5093 ms	335088 KiB

diameter

#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

const int NMAX = 1e5;

struct node_t{
    vector<pair<long long,int> > bst_nodes;
    long long lazy;
    long long bst;
    long long bst2;

    node_t(){
        bst_nodes = vector<pair<long long,int>>();
        lazy = 0;
        bst = 0;
        bst2 = -1e18;
    }

    node_t(long long val,int tag){
        bst_nodes = vector<pair<long long,int>>(1,{val,tag});
        lazy = 0;
        bst = val;
        bst2 = -1e18;
    }

    node_t operator + (const node_t &other){
        node_t ans;
        ans.lazy = 0;
        ans.bst = max(this->bst,other.bst);
        ans.bst2 = max(this->bst2,other.bst2);

        for(auto it:bst_nodes){
            ans.bst_nodes.push_back(it);
        }
        for(auto it:other.bst_nodes){
            ans.bst_nodes.push_back(it);
        }

        sort(ans.bst_nodes.begin(),ans.bst_nodes.end());
        reverse(ans.bst_nodes.begin(),ans.bst_nodes.end());

        int id = 1;

        while(id < (int)ans.bst_nodes.size() && ans.bst_nodes[id].second == ans.bst_nodes[0].second){
            id++;
        }

        if(id < (int)ans.bst_nodes.size()){
            ans.bst_nodes[1] = ans.bst_nodes[id];
            ans.bst_nodes.resize(2);
            ans.bst2 = max(ans.bst2,ans.bst_nodes[0].first + ans.bst_nodes[1].first);
        }
        else{
            ans.bst_nodes.resize(1);
        }

        for(auto it:ans.bst_nodes){
            ans.bst = max(ans.bst,it.first);
        }

        return ans;
    }

    void propag(long long val){
        lazy += val;
        for(auto &it:bst_nodes){
            it.first += val;
        }
        bst += val;
        bst2 += 2 * val;
    }
};

int tmp_tag[NMAX + 5];

class SegTree{
    int n;
    vector<node_t> aint;

    void build(int nod,int st,int dr){
        if(st == dr){
            aint[nod] = {node_t(0,tmp_tag[st])};
            return ;
        }
        int mid = (st + dr) / 2;
        build(nod * 2,st,mid);
        build(nod * 2 + 1,mid + 1,dr);
        aint[nod] = aint[nod * 2] + aint[nod * 2 + 1];
    }

    void update(int nod,int st,int dr,int l,int r,long long delta){
        if(st != dr && aint[nod].lazy != 0){
            aint[nod * 2].propag(aint[nod].lazy);
            aint[nod * 2 + 1].propag(aint[nod].lazy);
            aint[nod].lazy = 0;
        }
        if(r < st || l > dr){
            return ;
        }
        if(l <= st && dr <= r){
            aint[nod].propag(delta);
            return ;
        }

        int mid = (st + dr) / 2;

        update(nod * 2,st,mid,l,r,delta);
        update(nod * 2 + 1,mid + 1,dr,l,r,delta);

        aint[nod] = aint[nod * 2] + aint[nod * 2 + 1];
    }

public:

    SegTree(){
        n = 0;
        aint = vector<node_t> (vector<node_t> ());
    }

    SegTree(int n){
        this->n = n;
        this->aint = vector<node_t> (4 * n + 1,node_t());
        build(1,1,n);
    }

    void update(const pair<int,int> &segm,long long delta){
        update(1,1,n,segm.first,segm.second,delta);
    }

    long long query(){
        return max(aint[1].bst,aint[1].bst2);
    }
};

int n,q;
long long w;

pair<int,int> edge[NMAX + 5];
long long cost[NMAX + 5];

vector<int> graph[NMAX + 5];

int viz[NMAX + 5];
int weight[NMAX + 5];

void dfs(int nod,int tata){
    weight[nod] = 1;
    for(auto it:graph[nod]){
        if(it == tata || viz[it] == true){
            continue;
        }
        dfs(it,nod);
        weight[nod] += weight[it];
    }
}

vector<pair<int,pair<int,int>> > stuff[NMAX + 5];//(centroid,pos in lin of centroid)
SegTree trees[NMAX + 5];

set<pair<long long,int>> s;

void dfs2(int nod,int tata,const int &root,int &lst,int tag){
    if(nod != root){
        lst++;
        stuff[nod].push_back({root,{lst,0}});
        if(tag == root){
            tag = nod;    
        }
        tmp_tag[lst] = tag;
    }
    for(auto it:graph[nod]){
        if(it == tata || viz[it] == true){
            continue;
        }
        dfs2(it,nod,root,lst,tag);
    }
    if(nod != root){
        stuff[nod].back().second.second = lst;
    }
}

int centroid(int nod){
    dfs(nod,0);
    int root = nod;
    int total_weight = weight[nod];

    while(true){
        int bst = -1;
        for(auto it:graph[root]){
            if(nod != it && viz[it] == false && (bst == -1 || weight[bst] < weight[it])){
                bst = it;
            }
        }
        if(bst == -1 || weight[bst] * 2 <= total_weight){
            break;
        }
        nod = root;
        root = bst;
    }

    viz[root] = true;
    int a = 0;
    dfs2(root,0,root,a,root);
    trees[root] = SegTree(total_weight);
    s.insert({0,root});    

    for(auto it:graph[root]){
        if(viz[it] == false){
            centroid(it);
        }
    }

    return root;
}

int answer[NMAX + 5];

void update(pair<int,int> edge,long long c){
    if(stuff[edge.first].empty() == false && stuff[edge.first].back().first == edge.second){
        swap(edge.first,edge.second);
    }
    for(auto it:stuff[edge.second]){
        s.erase({answer[it.first],it.first});
        trees[it.first].update(it.second,c);
        answer[it.first] = trees[it.first].query();
        s.insert({answer[it.first],it.first});
    }
}

long long query(){
    return s.rbegin()->first;
}

int main(){

    scanf("%d %d %lld",&n,&q,&w);

    for(int i = 1;i < n;i++){
        scanf("%d %d %lld",&edge[i].first,&edge[i].second,&cost[i]);
        graph[edge[i].first].push_back(edge[i].second);
        graph[edge[i].second].push_back(edge[i].first);
    }

    int root = centroid(1);

    for(int i = 1;i < n;i++){
        update(edge[i],cost[i]);
    }

    long long last = 0;

    //for(int i = 1;i <= n;i++){printf("node %d\n",i);for(auto it:stuff[i])printf("deb %d %d %d\n",it.first,it.second.first,it.second.second);printf("\n");}

    while(q--){
        int d;
        long long e;
        scanf("%d %lld",&d,&e);
        d = (d + last) % (n - 1);d++;
        e = (e + last) % w;
        update(edge[d],e - cost[d]);
        cost[d] = e;
        last = query();
        printf("%lld\n",last);
    }

    return 0;
}

Compilation message (stderr)

diameter.cpp: In function 'int main()':
diameter.cpp:248:9: warning: unused variable 'root' [-Wunused-variable]
     int root = centroid(1);
         ^~~~
diameter.cpp:240:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %lld",&n,&q,&w);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:243:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %lld",&edge[i].first,&edge[i].second,&cost[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:261:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %lld",&d,&e);
         ~~~~~^~~~~~~~~~~~~~~~~

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