Submission #201500

#	Time	Username	Problem	Language	Result	Execution time	Memory
201500		georgerapeanu	Dynamic Diameter (CEOI19_diameter)	C++11	49 / 100	5054 ms	226940 KiB

diameter

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

using namespace std;

const int NMAX = 1e5;

struct data_t{
    int tree_id;
    int st;
    int dr;
    int father;

    bool operator < (const data_t &other)const{
        if(tree_id != other.tree_id){
            return tree_id < other.tree_id;
        }
        if(st != other.st){
            return st < other.st;
        }
        if(dr != other.dr){
            return dr < other.dr;
        }
        return father < other.father;
    }
};

class SegTree{
   
    int n;
    vector <long long> aint;
    vector <long long> lazy;

    void propag(int nod,int st,int dr){
        if(lazy[nod] == 0 || st == dr){
            return ;
        }
        aint[nod * 2] += lazy[nod];
        lazy[nod * 2] += lazy[nod];
        aint[nod * 2 + 1] += lazy[nod];
        lazy[nod * 2 + 1] += lazy[nod];
        lazy[nod] = 0;
    }

    void update(int nod,int st,int dr,int l,int r,long long delta){
        propag(nod,st,dr);
        if(dr < l || st > r){
            return ;
        }
        if(l <= st && dr <= r){
            aint[nod] += delta;
            lazy[nod] += 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] = max(aint[nod * 2],aint[nod * 2 + 1]);
    }

public:

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

    void update(int l,int r,long long val){
        update(1,1,n,l,r,val);
    }

    long long query(){
        return aint[1];
    }
};

int n,q;
long long w;
bool viz[NMAX + 5];
int weight[NMAX + 5];
vector<int> graph[NMAX + 5];

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

class RootPathSolver{

    int lst;
    int root;

    vector< SegTree > trees;

    unordered_map<int,data_t> stuff;
    set<pair<long long,int> > answers;//(best path,tree id)

    void dfs(int nod,int tata,int id){
        data_t tmp = {id,++lst,-1,tata};
        weight[nod] = 1;

        for(auto it:graph[nod]){
            if(it == tata || viz[it] == true){
                continue;
            }
            dfs(it,nod,id);
            weight[nod] += weight[it];
        }
        
        tmp.dr = lst;
        stuff[nod] = tmp;
    }

public:

    RootPathSolver(){
    }

    RootPathSolver(int root){
        this->root = root;
        int lst_id = -1;
        for(auto it:graph[root]){
            if(viz[it] == false){
                lst = 0;
                dfs(it,root,++lst_id);
                trees.push_back(SegTree(weight[it]));
                answers.insert({0,it});
            }
        }
    }

    void update(pair<int,int> edge,long long delta){
        data_t tmp = stuff[edge.second];
        if(edge.second == root || tmp.father != edge.first){
            swap(edge.second,edge.first);
            tmp = stuff[edge.second];
        }
        answers.erase({trees[tmp.tree_id].query(),tmp.tree_id});
        trees[tmp.tree_id].update(tmp.st,tmp.dr,delta);
        answers.insert({trees[tmp.tree_id].query(),tmp.tree_id});
    }

    long long query(){
        if(answers.empty()){
            return 0;
        }
        else if(answers.size() == 1){
            return answers.rbegin()->first;
        }
        else{
            return (answers.rbegin())->first + (next(answers.rbegin()))->first;
        }
    }

};

class Centroid{
    public:
    int root;

    vector<RootPathSolver> chestie;
    vector<vector<int> > history;
    set<pair<long long,int> > answers;

    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];
        }
    }

    void dfs_root(int nod,int tata,int root){
        if(root != nod){
            history[nod].push_back(root);
        }
        for(auto it:graph[nod]){
            if(viz[it] == true || it == tata){
                continue;
            }
            dfs_root(it,nod,root);
        }
    }

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

        int root = nod;

        while(true){
            int bst = -1;

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

        viz[root] = true;
        chestie[root] = RootPathSolver(root);
        dfs_root(root,0,root);

        answers.insert({0,root});

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

        return root;
    }

public:

    Centroid(int n){
        this->chestie = vector<RootPathSolver>(n + 1,RootPathSolver());
        this->history = vector<vector<int>>(n + 1,vector<int>());;
        this->root = centroid(1);
    }

    void update(pair<int,int> edge,long long delta){
        if(history[edge.first].size() > history[edge.second].size()){
            swap(edge.first,edge.second);
        }
        for(auto it:history[edge.second]){
            answers.erase({chestie[it].query(),it});
            chestie[it].update(edge,delta);
            answers.insert({chestie[it].query(),it});
        }
    }

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

const int LEN = 1 << 12;
char buff[LEN];
int ind = LEN - 1;

int i32(){
    int ans = 0;

    while(buff[ind] < '0' || buff[ind] > '9'){
        if(++ind >= LEN){
            ind = 0;
            fread(buff,1,LEN,stdin);
        }
    }
    
    while(!(buff[ind] < '0' || buff[ind] > '9')){
        ans = ans * 10 + buff[ind] - '0';
        if(++ind >= LEN){
            ind = 0;
            fread(buff,1,LEN,stdin);
        }
    }
    return ans;
}

long long i64(){
    long long ans = 0;

    while(buff[ind] < '0' || buff[ind] > '9'){
        if(++ind >= LEN){
            ind = 0;
            fread(buff,1,LEN,stdin);
        }
    }
    
    while(!(buff[ind] < '0' || buff[ind] > '9')){
        ans = ans * 10 + buff[ind] - '0';
        if(++ind >= LEN){
            ind = 0;
            fread(buff,1,LEN,stdin);
        }
    }
    return ans;
}

int main(){

    n = i32();
    q = i32();
    w = i64();

    for(int i = 1;i < n;i++){
        edge[i].first = i32();
        edge[i].second = i32();
        cost[i] = i64();
        graph[edge[i].first].push_back(edge[i].second);
        graph[edge[i].second].push_back(edge[i].first);
    }


    Centroid a(n);

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

    long long last = 0;

    while(q--){
        int d;
        long long e;
        
        d = i32();
        e = i64();

        d = (d + last) % (n - 1) + 1;
        e = (e + last) % w;

        a.update(edge[d],e - cost[d]);
        cost[d] = e;

        last = a.query();

        printf("%lld\n",last);
    }

    return 0;
}

Compilation message (stderr)

diameter.cpp: In member function 'int Centroid::centroid(int)':
diameter.cpp:228:21: warning: unused variable 'tmp' [-Wunused-variable]
                 int tmp = centroid(it);
                     ^~~
diameter.cpp: In function 'int i32()':
diameter.cpp:269:18: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
             fread(buff,1,LEN,stdin);
             ~~~~~^~~~~~~~~~~~~~~~~~
diameter.cpp:277:18: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
             fread(buff,1,LEN,stdin);
             ~~~~~^~~~~~~~~~~~~~~~~~
diameter.cpp: In function 'long long int i64()':
diameter.cpp:289:18: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
             fread(buff,1,LEN,stdin);
             ~~~~~^~~~~~~~~~~~~~~~~~
diameter.cpp:297:18: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
             fread(buff,1,LEN,stdin);
             ~~~~~^~~~~~~~~~~~~~~~~~

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