Submission #239991

#	Time	Username	Problem	Language	Result	Execution time	Memory
239991		karma	Dynamic Diameter (CEOI19_diameter)	C++14	49 / 100	5085 ms	251496 KiB

diameter

#include <bits/stdc++.h>
#define pb          emplace_back
#define ll          long long
#define fi          first
#define se          second
#define mp          make_pair
//#define int         int64_t

using namespace std;

const int N = (int)1e5 + 2;
const ll inf = 1ll << 60;
typedef pair<int, int> pii;

struct TTree { /// get max value in range, add x in a range
    vector<pair<ll, int>> st;
    vector<ll> lz;
    vector<int> l, h;
    vector<pii> range;
    int n; ll val;
    pair<ll, int> top;
    void init(int _n) {
        n = _n;
        l.resize(4 * n + 4);
        h.resize(l.size());
        st.resize(l.size());
        lz.resize(l.size());
        build(1, 0, n - 1);
    }
    void build(int x, int low, int high) {
        l[x] = low, h[x] = high;
        if(l[x] == h[x]) {
            st[x].se = l[x];
            return;
        }
        int mid = (low + high) >> 1;
        build(x << 1, low, mid);
        build(x << 1 | 1, mid + 1, high);
    }
    void down(int x) {
        if(lz[x] == 0 || l[x] == h[x]) return;
        st[x << 1].fi += lz[x], lz[x << 1] += lz[x];
        st[x << 1 | 1].fi += lz[x], lz[x << 1 | 1] += lz[x];
        lz[x] = 0;
    }
    inline pair<ll, int> Max(const pair<ll, int>& x, const pair<ll, int>& y) {
        if(x.fi > y.fi) return x;
        if(x.fi < y.fi) return y;
        return x;
    }
    void upd(int x, int low, int high, ll val) {
        down(x);
        if(l[x] > high || h[x] < low) return;
        if(low <= l[x] && h[x] <= high) {
            st[x].fi += val, lz[x] += val;
            return;
        }
        upd(x << 1, low, high, val);
        upd(x << 1 | 1, low, high, val);
        st[x] = Max(st[x << 1], st[x << 1 | 1]);
    }
    pair<ll, int> get(int x, int low, int high) {
        down(x);
        if(l[x] > high || h[x] < low) return mp(-inf, 0);
        if(l[x] >= low && h[x] <= high) return st[x];
        return Max(get(x << 1, low, high), get(x << 1 | 1, low, high));
    }
    void update(int l, int h, ll v) {upd(1, l, h, v);}
    pair<ll, int> query(int l, int h) {return get(1, l, h);}
    ll diameter() {
        top = query(0, n - 1);
        val = top.fi;
        update(range[top.se].fi, range[top.se].se, -top.fi);
        val += max((ll)query(0, n - 1).fi, 0ll);
        update(range[top.se].fi, range[top.se].se, top.fi);
        return val;
    }
};
vector<TTree> it;

struct TEdge {
    int u, v; ll w;
    vector<int> it;
    vector<pii> range;
} e[N];
vector<pii> adj[N];
ll W, dis[N];
int n, q, Time, head[N], in[N], out[N], sz[N], big[N];
bool del[N];

int find(int u) {
    function<void(int, int)> dfs = [&](int u, int p) {
        sz[u] = 1, big[u] = 0;
        for(auto v: adj[u]) {
            if(v.fi == p || del[v.fi]) continue;
            dfs(v.fi, u);
            sz[u] += sz[v.fi];
            if(sz[v.fi] > sz[big[u]]) big[u] = v.fi;
        }
    };
    dfs(u, -1);
    int cen = u;
    while(sz[big[cen]] * 2 >= sz[u] && big[cen]) cen = big[cen];
    return cen;
}

multiset<ll, greater<ll>> ans;
void centroid(int u) {
    int root = find(u);
    it.push_back({});
    function<void(int, int)> dfs = [&](int u, int p) {
        in[u] = ++Time;
        if(p == root) head[u] = u;
        else if(p != -1) head[u] = head[p];
        for(auto v: adj[u]) {
            if(del[v.fi] || v.fi == p) continue;
            dis[v.fi] = dis[u] + e[v.se].w;
            it.back().range.pb(v.se, v.fi);
            dfs(v.fi, u);
        }
        out[u] = Time;
    };
    Time = -2, dis[root] = 0;
    dfs(root, -1); del[root] = 1;
    if((int)it.back().range.size()) {
        it.back().init((int)it.back().range.size());
        for(auto& p: it.back().range) {
            e[p.fi].it.pb((int)it.size() - 1);
            e[p.fi].range.pb(in[p.se], out[p.se]);
            it.back().update(in[p.se], in[p.se], dis[p.se]);
            p.fi = in[head[p.se]], p.se = out[head[p.se]];
        }
        ans.insert(it.back().diameter());
    }
    for(auto v: adj[root]) {
        if(del[v.fi]) continue;
        centroid(v.fi);
    }
}

///40071305542068

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define Task        "test"
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    cin >> n >> q >> W;
    for(int i = 0; i < n - 1; ++i) {
        cin >> e[i].u >> e[i].v >> e[i].w;
        adj[e[i].u].pb(e[i].v, i);
        adj[e[i].v].pb(e[i].u, i);
    }
    centroid(1); ll w, lst = 0;
    //cout << *ans.begin() << '\n';
    for(int id, tree; q > 0; --q) {
        cin >> id >> w;
        id = (id + lst) % (n - 1);
        w = (w + lst) % W;
        for(int i = 0; i < e[id].it.size(); ++i) {
            tree = e[id].it[i];
            ans.erase(ans.find(it[tree].diameter()));
            it[tree].update((int)e[id].range[i].fi, (int)e[id].range[i].se, w - e[id].w);
            ans.insert(it[tree].diameter());
        }
        e[id].w = w;
        cout << (lst = *ans.begin()) << '\n';
    }
}

Compilation message (stderr)

diameter.cpp: In function 'int32_t main()':
diameter.cpp:163:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < e[id].it.size(); ++i) {
                        ~~^~~~~~~~~~~~~~~~~
diameter.cpp:148:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:149:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp: In function 'void centroid(int)':
diameter.cpp:113:29: warning: array subscript is below array bounds [-Warray-bounds]
         if(p == root) head[u] = u;
                       ~~~~~~^

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