Submission #201696

#	Time	Username	Problem	Language	Result	Execution time	Memory
201696		georgerapeanu	Dynamic Diameter (CEOI19_diameter)	C++11	49 / 100	5052 ms	162808 KiB

diameter

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

using namespace std;

const int NMAX = 1e5;

class SegTree{
public:
    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);
    }

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

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

struct edge_t{
    int u,v;
    long long cost;

    inline int other(int x){
        return u ^ v ^ x;
    }
};

struct data_t{
    int centroid;
    int tree_id;
    int st,dr;
};

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

edge_t edge[NMAX + 5];

vector<data_t> stuff[NMAX + 5];


const int LEN = 1 << 20;
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;
}

class RootSolver{
public:
    vector<SegTree> trees;
    set<pair<long long,int> > answer;
    int lst;

    void dfs(int nod,int tata,int centroid,int id,int edge_id){
        weight[nod] = 1;
        data_t tmp;
        lst++;
        tmp.centroid = centroid;
        tmp.tree_id = id;
        tmp.st = lst;
        for(auto it:graph[nod]){
            if(viz[edge[it].other(nod)] == true || edge[it].other(nod) == tata){
                continue;
            }
            dfs(edge[it].other(nod),nod,centroid,id,it);
            weight[nod] += weight[edge[it].other(nod)];
        }
        tmp.dr = lst;
        stuff[edge_id].push_back(tmp);
    }

public:

    RootSolver(){
    }

    RootSolver(int root){
        for(auto it:graph[root]){
            if(viz[edge[it].other(root)] == false){
                lst = 0;
                dfs(edge[it].other(root),root,root,trees.size(),it);
                answer.insert({0,trees.size()});
                trees.push_back(SegTree(weight[edge[it].other(root)]));
            }
        }
    }

    inline void update(const data_t &tmp,long long delta){
        answer.erase({trees[tmp.tree_id].query(),tmp.tree_id});
        trees[tmp.tree_id].update(tmp.st,tmp.dr,delta);
        answer.insert({trees[tmp.tree_id].query(),tmp.tree_id});
    }

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

class Centroid{
public:
    int root;
 
    vector<RootSolver> chestie;
    set<pair<long long,int> > answers;
 
    void dfs(int nod,int tata){
        weight[nod] = 1;
        for(auto it:graph[nod]){
            if(edge[it].other(nod) == tata || viz[edge[it].other(nod)] == true){
                continue;
            }
            dfs(edge[it].other(nod),nod);
            weight[nod] += weight[edge[it].other(nod)];
        }
    }
 
    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[edge[it].other(root)] == true || edge[it].other(root) == nod){
                    continue;
                }
                if(bst == -1 || weight[edge[it].other(root)] > weight[bst]){
                    bst = edge[it].other(root);
                }
            }
            if(bst != -1 && weight[bst] * 2 > total_weight){
                nod = root;
                root = bst;
            }
            else{
                break;
            }
        }

        viz[root] = true;
        chestie[root] = RootSolver(root);
 
        answers.insert({0,root});
 
        for(auto it:graph[root]){
            if(viz[edge[it].other(root)] == false){
                int tmp = centroid(edge[it].other(root));
            }
        }
 
        return root;
    }
 
public:
 
    Centroid(int n){
        this->chestie = vector<RootSolver>(n + 1,RootSolver());
        this->root = centroid(1);
    }
 
    inline void update(const data_t &tmp,long long delta){
        answers.erase({chestie[tmp.centroid].query(),tmp.centroid});
        chestie[tmp.centroid].update(tmp,delta);
        answers.insert({chestie[tmp.centroid].query(),tmp.centroid});
    }
 
    inline long long query(){
        return answers.rbegin()->first;
    }
};

int main(){

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

    for(int i = 1;i <= n;i++){
        stuff[i].reserve(20);
    }

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

    long long last = 0;

    Centroid a(n);

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

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

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

        for(auto it:stuff[d]){
            a.update(it,e - edge[d].cost);
        }
        edge[d].cost = e;

        last = a.query();

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

    return 0;
}

Compilation message (stderr)

diameter.cpp: In member function 'int Centroid::centroid(int)':
diameter.cpp:244:21: warning: unused variable 'tmp' [-Wunused-variable]
                 int tmp = centroid(edge[it].other(root));
                     ^~~
diameter.cpp: In function 'int i32()':
diameter.cpp:99: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:107: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:119: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:127: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