oj.uz

답안 #201483

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
201483 2020-02-10T17:30:57 Z georgerapeanu Dynamic Diameter (CEOI19_diameter) C++11
31 / 100
 814 ms 38424 KB 
#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

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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 6 ms 2680 KB Output is correct
3 Correct 9 ms 2680 KB Output is correct
4 Correct 22 ms 2936 KB Output is correct
5 Correct 84 ms 3832 KB Output is correct
6 Correct 6 ms 2680 KB Output is correct
7 Correct 6 ms 2812 KB Output is correct
8 Correct 7 ms 2808 KB Output is correct
9 Correct 9 ms 2808 KB Output is correct
10 Correct 31 ms 3064 KB Output is correct
11 Correct 127 ms 4216 KB Output is correct
12 Correct 16 ms 4372 KB Output is correct
13 Correct 16 ms 4372 KB Output is correct
14 Correct 19 ms 4372 KB Output is correct
15 Correct 50 ms 4628 KB Output is correct
16 Correct 186 ms 5780 KB Output is correct
17 Correct 304 ms 36888 KB Output is correct
18 Correct 325 ms 37016 KB Output is correct
19 Correct 323 ms 36888 KB Output is correct
20 Correct 372 ms 37016 KB Output is correct
21 Correct 749 ms 38424 KB Output is correct

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 2808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 678 ms 26192 KB Output is correct
2 Correct 684 ms 26104 KB Output is correct
3 Correct 670 ms 26232 KB Output is correct
4 Correct 689 ms 26360 KB Output is correct
5 Correct 721 ms 28188 KB Output is correct
6 Correct 751 ms 35264 KB Output is correct
7 Correct 711 ms 28024 KB Output is correct
8 Correct 702 ms 28024 KB Output is correct
9 Correct 698 ms 28040 KB Output is correct
10 Correct 725 ms 28296 KB Output is correct
11 Correct 814 ms 30048 KB Output is correct
12 Correct 788 ms 36692 KB Output is correct
13 Correct 687 ms 30968 KB Output is correct
14 Correct 681 ms 30968 KB Output is correct
15 Correct 681 ms 30968 KB Output is correct
16 Correct 715 ms 31264 KB Output is correct
17 Correct 748 ms 32720 KB Output is correct
18 Correct 791 ms 37696 KB Output is correct
19 Correct 664 ms 30876 KB Output is correct
20 Correct 679 ms 30968 KB Output is correct
21 Correct 686 ms 31096 KB Output is correct
22 Correct 726 ms 31352 KB Output is correct
23 Correct 773 ms 32720 KB Output is correct
24 Correct 756 ms 37924 KB Output is correct

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -