Submission #1232816

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232816		Tenis0206	Dynamic Diameter (CEOI19_diameter)	C++20	55 / 100	1105 ms	26640 KiB

diameter

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

using namespace std;

const int nmax = 1e5;

struct Edge
{
    int x, y, c;
};

int n, q, w;
Edge e[nmax + 5];
vector<pair<int,int>> G[nmax + 5];

int l[nmax + 5];
int t[nmax + 5];

int p[nmax + 5], u[nmax + 5];

int r[nmax + 5];

pair<int,int> ai[4 * nmax + 5];
int lazy[4 * nmax + 5];

pair<int,int> Merge(pair<int,int> a, pair<int,int> b)
{
    if(a > b)
    {
        return a;
    }
    return b;
}

void init(int nod, int a, int b)
{
    if(a == b)
    {
        ai[nod].second = l[a];
        return;
    }
    int mij = (a + b) >> 1;
    init(nod * 2, a, mij);
    init(nod * 2 + 1, mij + 1, b);
    ai[nod] = Merge(ai[nod * 2], ai[nod * 2 + 1]);
}

void propag(int nod)
{
    if(lazy[nod] == 0)
    {
        return;
    }
    ai[nod * 2].first += lazy[nod];
    ai[nod * 2 + 1].first += lazy[nod];
    lazy[nod * 2] += lazy[nod];
    lazy[nod * 2 + 1] += lazy[nod];
    lazy[nod] = 0;
}

void update(int ua, int ub, int val, int nod, int a, int b)
{
    if(ua <= a && ub >= b)
    {
        ai[nod].first += val;
        lazy[nod] += val;
        return;
    }
    propag(nod);
    int mij = (a + b) >> 1;
    if(ua <= mij)
    {
        update(ua, ub, val, nod * 2, a, mij);
    }
    if(ub > mij)
    {
        update(ua, ub, val, nod * 2 + 1, mij + 1, b);
    }
    ai[nod] = Merge(ai[nod * 2], ai[nod * 2 + 1]);
}

pair<int,int> query(int qa, int qb, int nod, int a, int b)
{
    if(qa <= a && qb >=b)
    {
        return ai[nod];
    }
    propag(nod);
    int mij = (a + b) >> 1;
    if(qa <= mij && qb > mij)
    {
        return Merge(query(qa, qb, nod*2, a, mij), query(qa, qb, nod*2+1, mij+1, b));
    }
    if(qa <= mij)
    {
        return query(qa, qb, nod*2, a, mij);
    }
    return query(qa, qb, nod*2+1, mij+1, b);
}

bool subtask2()
{
#ifdef home
    return false;
#endif // home
    return (n <= 5000 && q <= 5000);
}

bool subtask3()
{
    for(int i=1; i<n; i++)
    {
        if(e[i].x != 1 && e[i].y != 1)
        {
            return false;
        }
    }
    return true;
}

int dfs(int nod, int dad = 0)
{
    l[nod] = 0;
    vector<int> lst;
    int rez = 0;
    for(auto it : G[nod])
    {
        if(it.first == dad)
        {
            continue;
        }
        rez = max(rez, dfs(it.first, nod));
        lst.push_back(l[it.first] + e[it.second].c);
        l[nod] = max(l[nod], l[it.first] + e[it.second].c);
    }
    sort(lst.begin(), lst.end(), greater<int>());
    if(lst.size() == 0)
    {
        return rez;
    }
    if(lst.size() == 1)
    {
        rez = max(rez, lst.front());
        return rez;
    }
    rez = max(rez, lst[0] + lst[1]);
    return rez;
}

void solve2()
{
    int last = 0;
    for(int i=1; i<=q; i++)
    {
        int edge, val;
        cin>>edge>>val;
        edge = (edge + last) % (n - 1) + 1;
        val = (val + last) % w;
        e[edge].c = val;
        last = dfs(1);
        cout<<last<<'\n';
    }
}

void solve3()
{
    int last = 0;
    multiset<int, greater<int>> s;
    for(int i=1; i<n; i++)
    {
        s.insert(e[i].c);
    }
    for(int i=1; i<=q; i++)
    {
        int edge, val;
        cin>>edge>>val;
        edge = (edge + last) % (n - 1) + 1;
        val = (val + last) % w;
        auto it = s.lower_bound(e[edge].c);
        s.erase(it);
        s.insert(val);
        e[edge].c = val;
        last = 0;
        it = s.begin();
        last += *it;
        ++it;
        last += *it;
        cout<<last<<'\n';
    }
}

int cnt = 0;

void euler(int nod, int dad = 0, int root = 0)
{
    p[nod] = (++cnt);
    l[cnt] = nod;
    t[nod] = dad;
    r[nod] = root;
    for(auto it : G[nod])
    {
        if(it.first == dad)
        {
            continue;
        }
        if(dad == 0)
        {
            euler(it.first, nod, it.first);
        }
        else
        {
            euler(it.first, nod, root);
        }
    }
    u[nod] = cnt;
}

void solve5()
{
    euler(1);
    init(1, 1, n);
    for(int i=1; i<n; i++)
    {
        if(e[i].y == t[e[i].x])
        {
            swap(e[i].x, e[i].y);
        }
        update(p[e[i].y], u[e[i].y], e[i].c, 1, 1, n);
    }
    int last = 0;
    for(int i=1; i<=q; i++)
    {
        int edge, val;
        cin>>edge>>val;
        edge = (edge + last) % (n - 1) + 1;
        val = (val + last) % w;
        update(p[e[edge].y], u[e[edge].y], val - e[edge].c, 1, 1, n);
        e[edge].c = val;

        pair<int,int> Max1 = ai[1];
        pair<int,int> Max2 = {0, 0};
        if(p[r[Max1.second]] != 2)
        {
            Max2 = Merge(Max2, query(2, p[r[Max1.second]] - 1, 1, 1, n));
        }
        if(u[r[Max1.second]] != n)
        {
            Max2 = Merge(Max2, query(u[r[Max1.second]] + 1, n, 1, 1, n));
        }
        last = Max1.first + Max2.first;

        cout<<last<<'\n';
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
#ifdef home
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
#endif // home
    cin>>n>>q>>w;
    for(int i=1; i<n; i++)
    {
        cin>>e[i].x>>e[i].y>>e[i].c;
        G[e[i].x].push_back({e[i].y, i});
        G[e[i].y].push_back({e[i].x, i});
    }
    if(subtask2())
    {
        solve2();
        return 0;
    }
    if(subtask3())
    {
        solve3();
        return 0;
    }
    solve5();
    return 0;
}

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