Submission #201169

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
201169	2020-02-09T14:19:09 Z	georgerapeanu	Dynamic Diameter (CEOI19_diameter)	C++11	7 / 100	5000 ms	335088 KB

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

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.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	10 ms	8056 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	10 ms	8056 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	8184 KB	Output is correct
2	Correct	10 ms	8184 KB	Output is correct
3	Correct	13 ms	8184 KB	Output is correct
4	Correct	37 ms	8440 KB	Output is correct
5	Correct	150 ms	9340 KB	Output is correct
6	Correct	10 ms	8184 KB	Output is correct
7	Correct	11 ms	8568 KB	Output is correct
8	Correct	12 ms	8568 KB	Output is correct
9	Correct	17 ms	8568 KB	Output is correct
10	Correct	58 ms	8824 KB	Output is correct
11	Correct	245 ms	9848 KB	Output is correct
12	Correct	29 ms	11768 KB	Output is correct
13	Correct	30 ms	11768 KB	Output is correct
14	Correct	41 ms	11896 KB	Output is correct
15	Correct	94 ms	12152 KB	Output is correct
16	Correct	362 ms	13344 KB	Output is correct
17	Correct	507 ms	81988 KB	Output is correct
18	Correct	517 ms	81904 KB	Output is correct
19	Correct	540 ms	82000 KB	Output is correct
20	Correct	618 ms	82300 KB	Output is correct
21	Correct	1118 ms	83692 KB	Output is correct