Submission #1148716

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148716		CodeLakVN	Dynamic Diameter (CEOI19_diameter)	C++20	24 / 100	1276 ms	3908 KiB

diameter

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

#define task "DIAMETER"
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define F first
#define S second

template<class X, class Y>
    bool maximize(X &x, Y y) {
        if (x < y) {
            x = y;
            return true;
        }
        return false;
    }

const int N = (int)1e5 + 5;

int numNode, numQuery;
long long limit;
struct EDGE {
    int u, v,  c;
} edges[N];
pair<int, int> query[N];

typedef pair<int, long long> il;

namespace sub2 {
    const int N = (int)5e3 + 5;

    EDGE newEdges[N];

    vector<il> adj[N];

    long long res = 0;
    int x = 1;

    void dfs(int u, int p, long long cur) {
        if (maximize(res, cur)) x = u;
        for (il e : adj[u]) {
            if (e.F == p) continue;
            dfs(e.F, u, cur + e.S);
        }
    }

    long long findDiameter() {
        FOR(u, 1, numNode) adj[u].clear();
        FOR(i, 1, numNode - 1) {
            int u = newEdges[i].u, v = newEdges[i].v;
            long long c = newEdges[i].c;
            adj[u].push_back({v, c});
            adj[v].push_back({u, c});
        }
        x = 1;
        res = 0;
        dfs(1, -1, 0);
        dfs(x, -1, 0);
        return res;
    }

    void solve() {
        FOR(i, 1, numNode - 1) newEdges[i] = edges[i];
        long long last = 0;
        FOR(i, 1, numQuery) {
            int curEdge = (1LL * query[i].F + last) % (numNode - 1) + 1;
            long long curChange = (query[i].S + last) % limit;
            newEdges[curEdge].c = curChange;

            last = findDiameter();

            cout << last << "\n";
        }
    }
}

typedef pair<long long, long long> pll;

namespace sub4 {
    bool valid() {
        FOR(i, 1, numNode - 1) {
            int u = edges[i].u, v = edges[i].v;
            if (u > v) swap(u, v);
            if (v != u * 2 && v != u * 2 + 1) return false;
        }
        return true;
    }

    struct DATA {
        int firstMax, secondMax, firstBranch, secondBranch;
    } costToSon[N];

    vector<il> adj[N];

    int par[N];

    void update(DATA &cur, long long val, int branch) {
        if (val > cur.firstMax) {
            if (branch == cur.firstBranch) cur.firstMax = val;
            else {
                cur.secondMax = cur.firstMax;
                cur.secondBranch = cur.firstBranch;
                cur.firstMax = val;
                cur.firstBranch = branch;
            }
        }
        else if (val > cur.secondMax) {
            if (branch != cur.firstBranch) {
                cur.secondMax = val;
                cur.secondBranch = branch;
            }
        }
    }

    void dfs(int u, int p) {
        for (il e : adj[u]) {
            if (e.F == p) continue;
            int v = e.F;
            par[v] = u;
            dfs(v, u);
            long long cur = e.S + costToSon[v].firstMax;
            update(costToSon[u], cur, v);
        }
    }

    long long tree[4 * N];

    void update(int id, int l, int r, int pos, long long val) {
        if (l == r) { 
            tree[id] = val;
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid) update(2 * id, l, mid, pos, val);
        else update(2 * id + 1, mid + 1, r, pos, val);
        tree[id] = max(tree[2 * id], tree[2 * id + 1]);
    }

    long long weight[N];

    void updateQuery(int s) {
        while (s > 1) {
            update(costToSon[par[s]], costToSon[s].firstMax + weight[s], s);
            update(1, 1, numNode, par[s], costToSon[par[s]].firstMax + costToSon[par[s]].secondMax);
            s = par[s];
        }
    }

    void solve() {
        FOR(i, 1, numNode - 1) {
            int u = edges[i].u, v = edges[i].v;
            long long c = edges[i].c;
            adj[u].push_back({v, c});
            adj[v].push_back({u, c});
        }
        FOR(i, 1, numNode) costToSon[i] = {0, 0};
        dfs(1, -1);

        FOR(i, 1, numNode) update(1, 1, numNode, i, costToSon[i].firstMax + costToSon[i].secondMax);

        FOR(i, 1, numNode - 1) {
            int u = edges[i].u, v = edges[i].v;
            if (u > v) swap(u, v);
            weight[v] = edges[i].c;
        }
        
        long long last = 0;

        FOR(i, 1, numQuery) {
            int curEdge = (1LL * query[i].F + last) % (numNode - 1) + 1;
            long long curChange = (query[i].S + last) % limit;
            int u = max(edges[curEdge].u, edges[curEdge].v);
            weight[u] = curChange;

            updateQuery(u);

            last = tree[1];
            cout << last << "\n";
        }
    }
}

int main() {
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> numNode >> numQuery >> limit;
    FOR(i, 1, numNode - 1) {
        int u, v, c;
        cin >> u >> v >> c;
        edges[i] = {u, v, c};
    }
    FOR(i, 1, numQuery) {
        cin >> query[i].F >> query[i].S;
    }

    if (max(numNode, numQuery) <= 5000 && limit <= 10000) sub2::solve();
    else if (sub4::valid()) sub4::solve();

    return 0;
}

Compilation message (stderr)

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

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