Submission #1232800

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232800		Tenis0206	Dynamic Diameter (CEOI19_diameter)	C++20	31 / 100	1098 ms	15028 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];

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';
    }
}

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;
    }
    return 0;
}

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