Submission #1097291

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097291		Tien_Noob	Dynamic Diameter (CEOI19_diameter)	C++17	100 / 100	746 ms	36964 KiB

diameter

//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#define TASK "TESTCODE"
using namespace std;
const int N = 1e5;
int n, q;
long long w_mod;
vector<int> adj[N + 1];
int x[N], y[N];
int sz[N + 1], tin[N + 1], tout[N + 1];
int chain[N + 1], nchain, head[N + 1], par[N + 1], bc[N + 1];
long long d[N + 1], w[N];
int dfs_order[N + 1];
struct SegmentTree
{
    long long tree[4 * N + 1], lazy[4 * N + 1];
    SegmentTree()
    {
        memset(tree, -0x3f, sizeof(tree));
        memset(lazy, 0, sizeof(lazy));
    }
    void push(int v)
    {
        long long val = lazy[v];
        if (val == 0)
        {
            return ;
        }

        lazy[v] = 0;
        tree[2 * v] += val;
        lazy[2 * v] += val;

        tree[2 * v + 1] += val;
        lazy[2 * v + 1] += val;
    }
    void add(int v, int TreeL, int TreeR, int L, int R, long long val)
    {
        if (L > R)
        {
            return ;
        }
        if (TreeL == L && TreeR == R)
        {
            tree[v] += val;
            lazy[v] += val;
            return ;
        }
        push(v);
        int mid = (TreeL + TreeR)/2;
        add(v * 2, TreeL, mid, L, min(R, mid), val);
        add(v * 2 + 1, mid + 1, TreeR, max(L, mid + 1), R, val);
        tree[v] = max(tree[2 * v], tree[2 * v + 1]);
    }
    void add(int L, int R, long long val)
    {
        add(1, 1, n, L, R, val);
    }
    long long get(int v, int TreeL, int TreeR, int L, int R)
    {
        if (L > R)
        {
            return -1e18;
        }
        if (TreeL == L && TreeR == R)
        {
            return tree[v];
        }
        push(v);
        int mid = (TreeL + TreeR)/2;
        return max(get(v * 2, TreeL, mid, L, min(R, mid)), get(v * 2 + 1, mid + 1, TreeR, max(L, mid + 1), R));
    }
    long long get(int L, int R)
    {
        return get(1, 1, n, L, R);
    }
    void upd(int v, int TreeL, int TreeR, int pos, long long val)
    {
        if (TreeL == TreeR)
        {
            tree[v] = val;
            lazy[v] = 0;
            return ;
        }
        int mid = (TreeL + TreeR)/2;
        push(v);
        if (pos <= mid)
        {
            upd(v * 2, TreeL, mid, pos, val);
        }
        else
        {
            upd(v * 2 + 1, mid + 1, TreeR, pos, val);
        }
        tree[v] = max(tree[2 * v], tree[2 * v + 1]);
    }
    void upd(int pos, long long val)
    {
        upd(1, 1, n, pos, val);
    }
    int find_max()
    {
        int v = 1, L = 1, R = n;
        while(true)
        {
            if (L == R)
            {
                return L;
            }
            int mid = (L + R)/2;
            push(v);
            if (tree[2 * v] > tree[2 * v + 1])
            {
                v = v * 2;
                R = mid;
            }
            else
            {
                v = v * 2 + 1;
                L = mid + 1;
            }
        }
    }
} get_max_d, get_max_hld;
void preDFS(int u, int p)
{
    sz[u] = 1;
    for (int i : adj[u])
    {
        int v = x[i] ^ y[i] ^ u;
        if (v == p)
        {
            continue;
        }
        d[v] = d[u] + w[i];
        preDFS(v, u);
        sz[u] += sz[v];
    }
}
void buildHLD(int u, int p)
{
    int bigchild = -1;
    static int timer = 0;
    tin[u] = ++timer;
    dfs_order[timer] = u;

    chain[u] = nchain;
    if (head[nchain] == 0)
    {
        head[nchain] = u;
    }
    for (int i : adj[u])
    {
        int v = x[i] ^ y[i] ^ u;
        if (v == p)
        {
            continue;
        }
        if (x[i] == v)
        {
            swap(x[i], y[i]);
        }
        if (bigchild == - 1 || sz[v] > sz[bigchild])
        {
            bigchild = v;
        }
    }
    bc[u] = bigchild;
    if (bigchild != -1)
    {
        par[bigchild] = u;
        buildHLD(bigchild, u);
    }
    for (int i : adj[u])
    {
        int v = x[i] ^ y[i] ^ u;
        if (v == p || v == bigchild)
        {
            continue;
        }
        ++nchain;
        par[v] = u;
        buildHLD(v, u);
    }
    tout[u] = timer;
    get_max_d.upd(tin[u], d[u]);
}

long long cal(int u, int except)
{
    long long d_u = get_max_d.get(tin[u], tin[u]);

    long long d_other = d_u;
    if (except != -1)
    {
        d_other = max(d_other, get_max_d.get(tout[except] + 1, tout[u]));
        d_other = max(d_other, get_max_d.get(tin[u], tin[except] - 1));
    }
    return d_other - 2 * d_u;
}
long long query()
{
    long long res = 0;
    int p = get_max_d.find_max();
    p = dfs_order[p];
    int u = p;
    long long d_u = get_max_d.get(tin[u], tin[u]);
    while(p != 0)
    {
        int h = head[chain[p]];
        if (p != h)
        {
            res = max(res, d_u + get_max_hld.get(tin[h], tin[par[p]]));
        }
        p = par[h];
        if (p != 0)
        {
            res = max(res, d_u + cal(p, h));
        }
    }
    return res;
}

void upd(int i, long long nw_w)
{
    int u = y[i];
    long long dif = nw_w - w[i];
    w[i] = nw_w;
    get_max_d.add(tin[u], tout[u], dif);
    get_max_hld.add(tin[u], tout[u], -dif);

    while(true)
    {
        int h = head[chain[u]];
        int p = par[h];
        if (p == 0)
        {
            break;
        }
        get_max_hld.upd(tin[p], cal(p, bc[p]));
        u = p;
    }
}
void read()
{
    cin >> n >> q >> w_mod;
    for (int i = 1; i < n; ++ i)
    {
        int u, v;
        cin >> u >> v >> w[i];
        x[i] = u;
        y[i] = v;
        adj[u].push_back(i);
        adj[v].push_back(i);
    }
}
void solve()
{
    preDFS(1, 0);
    buildHLD(1, 0);
    for (int u = 1; u <= n; ++ u)
    {
        get_max_hld.upd(tin[u], cal(u, bc[u]));
    }
    long long last = 0;
    while(q--)
    {
        long long i, e;
        cin >> i >> e;
        i = (i + last) % (n - 1);
        ++i;
        e = (e + last) % w_mod;
        upd(i, e);
        last = query();
        cout << last << '\n';
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        //freopen(TASK".OUT", "w", stdout);
    }
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        //cout << "Case " << __ << ": ";
        read();
        solve();
    }
}

Compilation message (stderr)

diameter.cpp: In function 'int main()':
diameter.cpp:285:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  285 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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