Submission #1283356

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283356		icebear	Dynamic Diameter (CEOI19_diameter)	C++20	49 / 100	5053 ms	201284 KiB

diameter

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

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

template<class T>
    bool minimize(T &a, const T &b) {
        if (a > b) return a = b, true;
        return false;
    }

template<class T>
    bool maximize(T &a, const T &b) {
        if (a < b) return a = b, true;
        return false;
    }

#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORR(i,a,b) for(int i=(a); i>=(b); --i)
#define REP(i, n) for(int i=0; i<(n); ++i)
#define RED(i, n) for(int i=(n)-1; i>=0; --i)
#define MASK(i) (1LL << (i))
#define BIT(S, i) (((S) >> (i)) & 1)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define task "gen"
/*END OF TEMPLATE. ICEBEAR AND THE CAT WILL WIN VOI26 */

const int MOD = 1e9 + 7;
const int inf = 1e9 + 27092008;
const ll INF = 1e18 + 27092008;
const int N = 1e5 + 5;
struct Tree {
    vector<ii> nodes;
    vector<int> tin, tout, branch;
    Tree(int n = 0): tin(n + 5, 0), tout(n + 5, -1), branch(n + 5, 0), nodes() {}

    bool have_node(int &p, int u) {
        p = lower_bound(all(nodes), mp(u, -inf)) - nodes.begin();
        if (p < (int)nodes.size() && nodes[p].fi != u) p = inf;
        return p < (int)nodes.size();
    }
} tree[N];

struct SegmentTree {
    int n;
    vector<ll> node, lazy;
    SegmentTree(int _n = 0): n(_n), node(4 * _n + 5, 0), lazy(4 * _n + 5, 0) {}

    void pushDown(int id) {
        if (lazy[id]) {
            node[id << 1] += lazy[id];
            node[id << 1 | 1] += lazy[id];
            lazy[id << 1] += lazy[id];
            lazy[id << 1 | 1] += lazy[id];
            lazy[id] = 0;
        }
    }

    void update(int id, int l, int r, int u, int v, ll k) {
        if (l > v || r < u) return;
        if (u <= l && r <= v) {
            node[id] += k;
            lazy[id] += k;
            return;
        }
        pushDown(id);
        int mid = (l + r) >> 1;
        update(id << 1, l, mid, u, v, k);
        update(id << 1 | 1, mid + 1, r, u, v, k);
        node[id] = max(node[id << 1], node[id << 1 | 1]);
    }

    ll getMax(int id, int l, int r, int u, int v) {
        if (l > v || r < u) return -INF;
        if (u <= l && r <= v) return node[id];
        pushDown(id);
        int mid = (l + r) >> 1;
        return max(getMax(id << 1, l, mid, u, v), getMax(id << 1 | 1, mid + 1, r, u, v));
    }

    void update(int u, int v, ll k) {
        update(1, 1, n, u, v, k);
    }

    ll getMax(int u, int v) {
        return getMax(1, 1, n, u, v);
    }
} it[N];

int numNode, numQuery;
ll modW;
vector<pair<int, ll>> G[N];
pair<ii, ll> edge[N];
int sz[N], par[N];
bool isCentroid[N];

int get_sz(int u, int par) {
    sz[u] = 1;
    for(auto v : G[u]) if (v.fi != par && !isCentroid[v.fi])
        sz[u] += get_sz(v.fi, u);
    return sz[u];
}

int findCentroid(int u, int par, const int &subtree) {
    for(auto v : G[u]) if (v.fi != par && !isCentroid[v.fi] && sz[v.fi] * 2 > subtree)
        return findCentroid(v.fi, u, subtree);
    return u;
}

vector<ii> tree_pos[N];
int timer, root, cur;
ll mx;
void dfs(int u, int par, ll dist) {
    int pos = ++timer;
    maximize(mx, dist);
    tree[root].nodes.emplace_back(u, pos);
    it[root].update(pos, pos, dist);

    tree[root].tin[pos] = timer;
    tree[root].branch[pos] = cur;
    for(auto v : G[u]) if (v.fi != par && !isCentroid[v.fi])
        dfs(v.fi, u, dist + v.se);
    tree[root].tout[pos] = timer;
}

multiset<ll> dist_cen[N], all_dist;

void add_dist(int centroid) {
    if (!dist_cen[centroid].empty()) {
        auto it = dist_cen[centroid].end();
        it = prev(it);
        ll sum = *it;
        if (it != dist_cen[centroid].begin()) sum += *prev(it);
        all_dist.insert(sum);
    }
}

void del_dist(int centroid) {
    if (!dist_cen[centroid].empty()) {
        auto it = dist_cen[centroid].end();
        it = prev(it);
        ll sum = *it;
        if (it != dist_cen[centroid].begin()) sum += *prev(it);
        all_dist.erase(all_dist.find(sum));
    }
}

int depth_cen[N];
void buildCentroid(int u, int pre) {
    int centroid = findCentroid(u, -1, get_sz(u, -1));
    isCentroid[centroid] = true;
    par[centroid] = pre;
    depth_cen[centroid] = depth_cen[pre] + 1;

    it[centroid] = SegmentTree(sz[u]);
    tree[centroid] = Tree(sz[u]);
    tree[centroid].nodes.emplace_back(centroid, 0);

    timer = 0;
    root = centroid;
    for(auto v : G[centroid]) if (!isCentroid[v.fi]) {
        cur = timer + 1;
        mx = -INF;
        dfs(v.fi, -1, v.se);
        dist_cen[centroid].insert(mx);
    }
    add_dist(centroid);
    for(auto v : G[centroid]) if (!isCentroid[v.fi])
        buildCentroid(v.fi, centroid);
}

void update(int x, int y, ll add) {
    int cen = x;
    while(cen > 0) {
        int pos_x, pos_y;
        if (tree[cen].have_node(pos_x, x) && tree[cen].have_node(pos_y, y)) {
            int p = max(tree[cen].nodes[pos_x].se, tree[cen].nodes[pos_y].se);
            int segment = tree[cen].branch[p];

            del_dist(cen);
            ll max_dist = it[cen].getMax(tree[cen].tin[segment], tree[cen].tout[segment]);
            dist_cen[cen].erase(dist_cen[cen].find(max_dist));

            it[cen].update(tree[cen].tin[p], tree[cen].tout[p], add);

            max_dist = it[cen].getMax(tree[cen].tin[segment], tree[cen].tout[segment]);
            dist_cen[cen].insert(max_dist);
            add_dist(cen);
        }
        cen = par[cen];
    }
}

void init(void) {
    cin >> numNode >> numQuery >> modW;
    FOR(i, 0, numNode - 2) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        edge[i] = mp(mp(u, v), w);
        G[u].pb(mp(v, w));
        G[v].pb(mp(u, w));
    }
}

void process(void) {
    buildCentroid(1, 0);
    FOR(i, 1, numNode) sort(all(tree[i].nodes));
    FOR(i, 0, numNode - 2) if (depth_cen[edge[i].fi.fi] < depth_cen[edge[i].fi.se])
        swap(edge[i].fi.fi, edge[i].fi.se);

    ll ans = 0;
    while(numQuery--) {
        int index;
        ll weight;
        cin >> index >> weight;
        index = (index + ans) % (numNode - 1);
        weight = (weight + ans) % modW;

        update(edge[index].fi.fi, edge[index].fi.se, weight - edge[index].se);
        edge[index].se = weight;
        cout << (ans = *all_dist.rbegin()) << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int tc = 1;
//    cin >> tc;
    while(tc--) {
        init();
        process();
    }
    return 0;
}

Compilation message (stderr)

diameter.cpp: In function 'int main()':
diameter.cpp:237:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  237 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:238:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  238 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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