제출 #996585

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
996585		Trustfulcomic	Dynamic Diameter (CEOI19_diameter)	C++14	31 / 100	5067 ms	321456 KiB

diameter

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> ii;

vector<ll> vahy;
multiset<ll> maxima_centroids;

struct Intervalac{
    vector<ll> lenost;
    vector<ll> maxima;
};

struct Centroid{
    int node;
    map<int,int> next_centroid;
    map<int,ii> edge_interval;
    int listy;
    Intervalac intervalac;
    multiset<ll> maxima;
    map<int,ii> podstromy;
};

vector<Centroid> centroids;

int int_pow(int x, int e){
    if (e == 0) return 1;
    int m = int_pow(x, e/2);
    if (e%2 == 0) return m*m;
    else return m*m*x;
}

int dfs(vector<bool>& is_centroid, vector<vector<ii>>& strom, map<int,int>& pocty, int parent, int current){
    int res = 1;
    for (auto [_, i] : strom[current]){
        if (i == parent || is_centroid[i]) continue;
        res += dfs(is_centroid, strom, pocty, current, i);
    }
    pocty[current] = res;
    return res;
}

ii dfs2(vector<bool>& is_centroid, vector<vector<ii>>& strom, map<int, ii>& edge_interval, int& found, int parent, int current, vector<int>& indexy_hran, map<int,ii>& podstromy){
    ii res = {INT_MAX, INT_MIN};

    for (auto [i, j] : strom[current]){
        indexy_hran.push_back(i);
        if (j == parent || is_centroid[j]) continue;
        ii returned = dfs2(is_centroid, strom, edge_interval, found, current, j, indexy_hran, podstromy);
        edge_interval[i] = returned;

        if (parent == -1){
            for (int k : indexy_hran){
                podstromy[k] = returned;
            }
            indexy_hran.clear();
        }

        res.first = min(res.first, returned.first);
        res.second = max(res.second, returned.second);
    }

    if (res.first == INT_MAX){
        res = {found, found};
        found++;
    }

    return res;
}

Intervalac create_intervalac(int n){
    Intervalac res;
    while(n & (n - 1)) n++;
    res.maxima = vector<ll>(2*n, 0);
    res.lenost = vector<ll>(2*n, 0);
    return res;
}

vector<int> find_centroids(vector<bool>& is_centroid, vector<vector<ii>>& strom, int start){
    maxima_centroids.insert(0);
    map<int, int> pocty;
    dfs(is_centroid, strom, pocty, -1, start);

    int current = start;

    while (true){
        int go_to = -1;

        for (auto [_, i] : strom[current]){
            if (is_centroid[i]) continue;
            if (pocty[i] > pocty[current]/2){
                go_to = i;
                break;
            }
        }

        if (go_to == -1) break;
        pocty[current] -= pocty[go_to];
        pocty[go_to] += pocty[current];
        current = go_to;
    }

    if (pocty[current] == 1) return {};

    Centroid centr;
    centr.node = current;
    is_centroid[current] = true;

    int found = 0;
    vector<int> indexy_hran;
    dfs2(is_centroid, strom, centr.edge_interval, found, -1, centr.node, indexy_hran, centr.podstromy);
    centr.listy = found;

    for (int i = 0; i<strom[centr.node].size(); i++){
        centr.maxima.insert(0);
    }

    centr.intervalac = create_intervalac(centr.listy);

    vector<int> sousedi;
    for (auto [i, j] : strom[current]){
        if (is_centroid[j]) continue;
        sousedi.push_back(i);
        vector<int> sousedi_sousedu = find_centroids(is_centroid, strom, j);
        for (int k : sousedi_sousedu) {
            sousedi.push_back(k);
            centr.next_centroid[k] = centroids.size()-1;
        }
    }

    centroids.push_back(centr);
    return sousedi;
}

ll get_max(Intervalac& inter, int i, int l, int r, int a, int b){
    inter.maxima[i] += inter.lenost[i];
    if (2*i< inter.lenost.size()){
        inter.lenost[2*i] += inter.lenost[i];
        inter.lenost[2*i+1] += inter.lenost[i];
    }
    inter.lenost[i] = 0;

    if (l == a && r == b){
        return inter.maxima[i];
    } else if (r <= (a+b)/2){
        return get_max(inter, 2*i, l, r, a, (a+b)/2);
    } else if (l >= (a+b)/2){
        return get_max(inter, 2*i+1, l, r, (a+b)/2, b);
    } else {
        return max(get_max(inter, 2*i, l, (a+b)/2, a, (a+b)/2),get_max(inter, 2*i+1, (a+b)/2, r, (a+b)/2, b));
    }
}

void vyres_lesnost(Intervalac& inter, int i){
    inter.maxima[i] += inter.lenost[i];
    if (2*i< inter.lenost.size()){
        inter.lenost[2*i] += inter.lenost[i];
        inter.lenost[2*i+1] += inter.lenost[i];
    }
    inter.lenost[i] = 0;
}

void set_val(Intervalac& inter, int i, int l, int r, int a, int b, ll add){
    vyres_lesnost(inter, i);

    if (l == a && r == b){
        inter.lenost[i] = add;
    } else if (r <= (a+b)/2){
        set_val(inter, 2*i, l, r, a, (a+b)/2, add);
    } else if (l >= (a+b)/2){
        set_val(inter, 2*i+1, l, r, (a+b)/2, b, add);
    } else {
        set_val(inter, 2*i, l, (a+b)/2, a, (a+b)/2, add);
        set_val(inter, 2*i+1, (a+b)/2, r, (a+b)/2, b, add);
    }

    if (2*i < inter.lenost.size()){
        vyres_lesnost(inter, 2*i);
        vyres_lesnost(inter, 2*i+1);
        inter.maxima[i] = max(inter.maxima[2*i], inter.maxima[2*i+1]);
    }
}

void update(Centroid& centr, ll hrana, ll set_to){
    ll maximum_centroidu = 0;
    auto it = centr.maxima.end();
    it--;
    maximum_centroidu += *it;
    if (it != centr.maxima.begin()){
        it--;
        maximum_centroidu += *it;
    }
    maxima_centroids.erase(maxima_centroids.find(maximum_centroidu));

    centr.maxima.erase(centr.maxima.find(get_max(centr.intervalac, 1, centr.podstromy[hrana].first, centr.podstromy[hrana].second+1, 0, centr.intervalac.maxima.size()/2)));
    set_val(centr.intervalac, 1, centr.edge_interval[hrana].first, centr.edge_interval[hrana].second+1, 0, centr.intervalac.maxima.size()/2, set_to-vahy[hrana]);
    centr.maxima.insert(get_max(centr.intervalac, 1, centr.podstromy[hrana].first, centr.podstromy[hrana].second+1, 0, centr.intervalac.maxima.size()/2));
    
    maximum_centroidu = 0;
    it = centr.maxima.end();
    it--;
    maximum_centroidu += *it;
    if (it != centr.maxima.begin()){
        it--;
        maximum_centroidu += *it;
    }
    maxima_centroids.insert(maximum_centroidu);

    if (centr.next_centroid.find(hrana) != centr.next_centroid.end())
    update(centroids[centr.next_centroid[hrana]], hrana, set_to);
}

int main(){
    int n,q; cin >> n >> q;
    ll w; cin >> w;
    vahy.resize(n-1);

    vector<vector<ii>> strom(n);
    for (int i = 0; i<n-1; i++){
        int a,b; cin >> a >> b;
        ll c; cin >> c;

        vahy[i] = c;
        strom[a-1].push_back({i, b-1});
        strom[b-1].push_back({i, a-1});
    }

    vector<bool> is_centroid(n, false);
    find_centroids(is_centroid, strom, 0);
    for (int i = 0; i<n-1; i++){
        update(centroids.back(), i, 2*vahy[i]);
    }

    ll last = 0;

    for (int i = 0 ; i<q; i++){
        ll d; cin >> d;
        ll e; cin >> e;

        update(centroids.back(), (d+last)%(n-1), (e+last)%w);
        vahy[(d+last)%(n-1)] = (e+last)%w;

        last = *maxima_centroids.rbegin();
        cout << last << endl;
    }
}

컴파일 시 표준 에러 (stderr) 메시지

diameter.cpp: In function 'int dfs(std::vector<bool>&, std::vector<std::vector<std::pair<int, int> > >&, std::map<int, int>&, int, int)':
diameter.cpp:36:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |     for (auto [_, i] : strom[current]){
      |               ^
diameter.cpp: In function 'ii dfs2(std::vector<bool>&, std::vector<std::vector<std::pair<int, int> > >&, std::map<int, std::pair<int, int> >&, int&, int, int, std::vector<int>&, std::map<int, std::pair<int, int> >&)':
diameter.cpp:47:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |     for (auto [i, j] : strom[current]){
      |               ^
diameter.cpp: In function 'std::vector<int> find_centroids(std::vector<bool>&, std::vector<std::vector<std::pair<int, int> > >&, int)':
diameter.cpp:90:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   90 |         for (auto [_, i] : strom[current]){
      |                   ^
diameter.cpp:115:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     for (int i = 0; i<strom[centr.node].size(); i++){
      |                     ~^~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:122:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  122 |     for (auto [i, j] : strom[current]){
      |               ^
diameter.cpp: In function 'll get_max(Intervalac&, int, int, int, int, int)':
diameter.cpp:138:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |     if (2*i< inter.lenost.size()){
      |         ~~~^~~~~~~~~~~~~~~~~~~~~
diameter.cpp: In function 'void vyres_lesnost(Intervalac&, int)':
diameter.cpp:157:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |     if (2*i< inter.lenost.size()){
      |         ~~~^~~~~~~~~~~~~~~~~~~~~
diameter.cpp: In function 'void set_val(Intervalac&, int, int, int, int, int, ll)':
diameter.cpp:178:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |     if (2*i < inter.lenost.size()){
      |         ~~~~^~~~~~~~~~~~~~~~~~~~~

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