Submission #201483

#	Time	Username	Problem	Language	Result	Execution time	Memory
201483		georgerapeanu	Dynamic Diameter (CEOI19_diameter)	C++11	31 / 100	814 ms	38424 KiB

diameter

#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <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;

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

    void dfs(int nod,int tata,int id){
        stuff[nod] = {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];
        }

        stuff[nod].dr = lst;
    }

public:

    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){
        if(edge.second == root || stuff[edge.second].father != edge.first){
            swap(edge.second,edge.first);
        }
        answers.erase({trees[stuff[edge.second].tree_id].query(),stuff[edge.second].tree_id});
        trees[stuff[edge.second].tree_id].update(stuff[edge.second].st,stuff[edge.second].dr,delta);
        answers.insert({trees[stuff[edge.second].tree_id].query(),stuff[edge.second].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;
        }
    }

};

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

    RootPathSolver chestie(1);

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

    long long last = 0;

    while(q--){
        int d;
        long long e;
        
        scanf("%d %lld",&d,&e);

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

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

        last = chestie.query();

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

    return 0;
}

Compilation message (stderr)

diameter.cpp: In function 'int main()':
diameter.cpp:158: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:161: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:178: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: 24 / 24
• Subtask 6: 0 / 27