Submission #997131

#	Time	Username	Problem	Language	Result	Execution time	Memory
997131		Trustfulcomic	Dynamic Diameter (CEOI19_diameter)	C++14	100 / 100	3839 ms	108032 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;
};

vector<vector<int>> next_centroid;
vector<vector<ii>> edge_interval;
vector<vector<ii>> podstromy;

struct Centroid{
    int node;
    int depth;
    /* 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, int& found, int parent, int current, vector<int>& indexy_hran, int centroid_depth){
    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, found, current, j, indexy_hran, centroid_depth);
        edge_interval[centroid_depth][i] = returned;

        if (parent == -1){
            for (int k : indexy_hran){
                podstromy[centroid_depth][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, int centroid_depth){
    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;
    centr.depth = centroid_depth;

    int found = 0;
    vector<int> indexy_hran;
    dfs2(is_centroid, strom, found, -1, centr.node, indexy_hran, centr.depth);
    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, centroid_depth+1);
        for (int k : sousedi_sousedu) {
            sousedi.push_back(k);
            next_centroid[centr.depth][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, podstromy[centr.depth][hrana].first, podstromy[centr.depth][hrana].second+1, 0, centr.intervalac.maxima.size()/2)));
    set_val(centr.intervalac, 1, edge_interval[centr.depth][hrana].first, edge_interval[centr.depth][hrana].second+1, 0, centr.intervalac.maxima.size()/2, set_to-vahy[hrana]);
    centr.maxima.insert(get_max(centr.intervalac, 1, podstromy[centr.depth][hrana].first, podstromy[centr.depth][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 (next_centroid[centr.depth][hrana] != -1)
    update(centroids[next_centroid[centr.depth][hrana]], hrana, set_to);
}

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

    next_centroid = vector<vector<int>>(log2(n)+2, vector<int>(n-1, -1));
    edge_interval = vector<vector<ii>>(log2(n)+2, vector<ii>(n-1));
    podstromy = vector<vector<ii>>(log2(n)+2, vector<ii>(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, 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;
    }
}

Compilation message (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:41:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |     for (auto [_, i] : strom[current]){
      |               ^
diameter.cpp: In function 'ii dfs2(std::vector<bool>&, std::vector<std::vector<std::pair<int, int> > >&, int&, int, int, std::vector<int>&, int)':
diameter.cpp:52:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |     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, int)':
diameter.cpp:95:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   95 |         for (auto [_, i] : strom[current]){
      |                   ^
diameter.cpp:121: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]
  121 |     for (int i = 0; i<strom[centr.node].size(); i++){
      |                     ~^~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:128:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  128 |     for (auto [i, j] : strom[current]){
      |               ^
diameter.cpp: In function 'll get_max(Intervalac&, int, int, int, int, int)':
diameter.cpp:144:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |     if (2*i< inter.lenost.size()){
      |         ~~~^~~~~~~~~~~~~~~~~~~~~
diameter.cpp: In function 'void vyres_lesnost(Intervalac&, int)':
diameter.cpp:163:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |     if (2*i< inter.lenost.size()){
      |         ~~~^~~~~~~~~~~~~~~~~~~~~
diameter.cpp: In function 'void set_val(Intervalac&, int, int, int, int, int, ll)':
diameter.cpp:184:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  184 |     if (2*i < inter.lenost.size()){
      |         ~~~~^~~~~~~~~~~~~~~~~~~~~

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