Submission #1119922

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119922		LonlyR	Dynamic Diameter (CEOI19_diameter)	C++17	48 / 100	913 ms	36132 KiB

diameter

#include<bits/stdc++.h>
#define int long long
#define ii pair<int,int>

using namespace std;
const int maxn = 1e5 + 5;
int n, q, W;
array<int, 2> qr[maxn];
vector<int> adj[maxn];
vector<array<int, 2>> edges;

struct sub1{
    int dp[maxn][2], ans;
    void dfs(int x = 1, int p = 1)
    {
        dp[x][0] = dp[x][1] = 0;
        for (int id : adj[x])
        {
            int i = edges[id][0] - x, w = edges[id][1];
            if (i == p) continue;
            dfs(i, x);
            if (dp[x][0] < dp[i][0] + w)
                dp[x][1] = dp[x][0], dp[x][0] = dp[i][0] + w;
            else dp[x][1] = max(dp[x][1], dp[i][0] + w);
        }
        ans = max(ans, dp[x][0] + dp[x][1]);
    }
    sub1()
    {
        for (int i = 1, last = 0; i <= q; i++)
        {
            int id = qr[i][0], w = qr[i][1];
            id = (id + last) % (n - 1);
            w = (w + last) % W;
            edges[id][1] = w;
            ans = 0;
            dfs();
            cout << (last = ans) << "\n";
        }
    }
};

void subtask1()
{
    sub1 gold_voi;
}

void subtask3()
{
    vector<int> a(n + 1);
    set<pair<int,int>> s;
    for (auto [u, v] : edges)
        a[u - 1] = v,
        s.emplace(v, u - 1);
    for (int i = 1, last = 0; i <= q; i++)
    {
        int id = qr[i][0], w = qr[i][1];
        id = (id + last) % (n - 1);
        w = (w + last) % W;
        int node = edges[id][0] - 1;
        s.erase(s.find({a[node], node}));
        a[node] = w;
        s.emplace(a[node], node);
        int ans = 0;
        auto it = s.rbegin();
        if (s.size())
            ans += it -> first;
        if (s.size() >= 2)
            ans += prev(it) -> first;
        cout << (last = ans) << "\n";
    }
}

struct sub4{
    int dp[maxn][2], mx[maxn], h[maxn], node[maxn];
    int ans;
    void dfs(int x = 1, int p = 1)
    {
        h[x] = h[p] + 1;
        dp[x][0] = dp[x][1] = 0;
        mx[x] = 0;
        for (int id : adj[x])
        {
            int i = edges[id][0] - x, w = edges[id][1];
            if (i == p) continue;
            node[id] = x;
            dfs(i, x);
            if (dp[x][0] < dp[i][0] + w)
                dp[x][1] = dp[x][0], dp[x][0] = dp[i][0] + w;
            else dp[x][1] = max(dp[x][1], dp[i][0] + w);
            mx[x] = max(mx[x], mx[i]);
        }
        mx[x] = max(mx[x], dp[x][0] + dp[x][1]);
    }
    void upd(int x)
    {
        if (x) return;
        mx[x] = 0;
        for (int id : adj[x])
        {
            int i = edges[id][0] - x, w = edges[id][1];
            if (i == x / 2) continue;
            if (i == x * 2)
                dp[x][0] = max(dp[i][0], dp[i][1]) + w;
            else dp[x][1] = max(dp[i][0], dp[i][1]) + w;
            mx[x] = max(mx[x], mx[i]);
        }
        mx[x] = max(mx[x], dp[x][0] + dp[x][1]);
        ans = max(ans, mx[x]);
        upd(x / 2);
    }
    sub4()
    {
        h[1] = 0;
        dfs();
        for (int i = 1, last = 0; i <= q; i++)
        {
            int id = qr[i][0], w = qr[i][1];
            id = (id + last) % (n - 1);
            w = (w + last) % W;
            edges[id][1] = w;
            ans = 0;
            upd(node[id]);
            cout << (last = ans) << "\n";
        }
    }
};

void subtask4()
{
    sub4 gold_voi;
}

struct sub5{
    int seg[4 * maxn], lz[4 * maxn], node[maxn], in[maxn], out[maxn], head[maxn];
    int cnt = 0;
    inline void add(int id, int val)
    {
        seg[id] += val;
        lz[id] += val;
    }
    inline void down(int id)
    {
        if (lz[id] == 0) return;
        add(id * 2, lz[id]);
        add(id * 2 + 1, lz[id]);
        lz[id] = 0;
    }
    void upd(int lx, int rx, int val, int id = 1, int l = 1, int r = n)
    {
        if (lx > r || l > rx) return;
        if (lx <= l && r <= rx) return add(id, val);
        int mid = (l + r) / 2;
        down(id);
        upd(lx, rx, val, id * 2, l, mid);
        upd(lx, rx, val, id * 2 + 1, mid + 1, r);
        seg[id] = max(seg[id * 2], seg[id * 2 + 1]);
    }
    int qry(int lx, int rx, int id = 1, int l = 1, int r = n)
    {
        if (lx > r || l > rx) return 0;
        if (lx <= l && r <= rx) return seg[id];
        int mid = (l + r) / 2;
        down(id);
        return max(qry(lx, rx, id * 2, l, mid), qry(lx, rx, id * 2 + 1, mid + 1, r));
    }
    void dfs(int x = 1, int p = 1, int w = 0, int top = -1)
    {
        in[x] = ++cnt;
        head[x] = top;
        for (int id : adj[x])
        {
            int i = edges[id][0] - x, w = edges[id][1];
            if (i == p) continue;
            int t = top;
            if (t == -1)
                t = i;
            node[id] = i;
            dfs(i, x, w, t);
        }
        out[x] = cnt;
        upd(in[x], out[x], w);
    }
    sub5()
    {
        dfs();
        vector<int> a(n + 1);
        set<pair<int,int>> s;
        for (int id : adj[1])
        {
            int i = edges[id][0] - 1;
            a[i] = qry(in[i], out[i]);
            s.emplace(a[i], i);
        }
        for (int i = 1, last = 0; i <= q; i++)
        {
            int id = qr[i][0], w = qr[i][1];
            id = (id + last) % (n - 1);
            w = (w + last) % W;
            int x = node[id];
            upd(in[x], out[x], w - edges[id][1]);
            edges[id][1] = w;
            x = head[x];
            s.erase(s.find({a[x], x}));
            a[x] = qry(in[x], out[x]);
            s.emplace(a[x], x);
            int ans = 0;
            auto it = s.rbegin();
            if (s.size())
                ans += it -> first;
            if (s.size() >= 2)
                ans += prev(it) -> first;
            cout << (last = ans) << "\n";
        }
    }
};

void subtask5()
{
    sub5 gold_voi;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    cin >> n >> q >> W;
    int s3 = 1, s4 = 1;
    for (int i = 1, u, v, w; i < n; i++)
    {
        cin >> u >> v >> w;
        if (u > v) swap(u, v);
        adj[u].emplace_back(edges.size());
        adj[v].emplace_back(edges.size());
        edges.push_back({u + v, w});
        s3 &= (u == 1 || v == 1);
        s4 &= (u * 2 == v || u * 2 + 1 == v);
    }
    for (int i = 1; i <= q; i++)
        cin >> qr[i][0] >> qr[i][1];
    if (max(n, q) <= 5000)
        subtask1();
    else if (s3)
        subtask3();
    else if (s4)
        subtask4();
    else subtask5();
}

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