제출 #1307988

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307988		HoriaHaivas	Dynamic Diameter (CEOI19_diameter)	C++20	42 / 100	5096 ms	27608 KiB

diameter

#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int range_rng(int l, int r)
{
    return uniform_int_distribution<int>(l,r)(rng);
}


struct muchie
{
    int a;
    int b;
    int c;
};

struct ceva
{
    int to;
    int w;
};

struct cmp
{
    bool operator()(ceva a, ceva b) const
    {
         return a.to<b.to;///efectiv orice
    }
};

pair<int,int> mxs[100005];
muchie edge[100005];
set<ceva,cmp> nodes[100005];
multiset<int> rez;
int p[100005];

void mergemax(int parent, int child, int cost)
{
    if (mxs[child].first+cost>mxs[parent].first)
    {
        mxs[parent].second=mxs[parent].first;
        mxs[parent].first=mxs[child].first+cost;
    }
    else if (mxs[child].first+cost>=mxs[parent].second)
    {
        mxs[parent].second=mxs[child].first+cost;
    }
}

void dfs(int node, int parent)
{
    mxs[node].first=0;
    mxs[node].second=0;
    for (auto x : nodes[node])
    {
         if (x.to!=parent)
         {
             p[x.to]=node;
             dfs(x.to,node);
             mergemax(node,x.to,x.w);
         }
    }
    rez.insert(mxs[node].first+mxs[node].second);
}

void update(int node)
{
    rez.erase(rez.find(mxs[node].first+mxs[node].second));
    mxs[node].first=0;
    mxs[node].second=0;
    for (auto x : nodes[node])
    {
         if (x.to!=p[node])
         {
             mergemax(node,x.to,x.w);
         }
    }
    rez.insert(mxs[node].first+mxs[node].second);
    if (p[node]!=0)
    update(p[node]);
}

signed main()
{
    /*
    ifstream fin("arbore.in");
    ofstream fout("arbore.out");
    */
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,q,w,i,j,a,b,c,d,e,last,parent,child;
    cin >> n >> q >> w;
    for (i=1;i<=n-1;i++)
    {
         cin >> a >> b >> c;
         nodes[a].insert({b,c});
         nodes[b].insert({a,c});
         edge[i]={a,b,c};
    }
    dfs(1,-1);
    last=0;
    for (i=1;i<=q;i++)
    {
         cin >> d >> e;
         d=(d+last)%(n-1);
         d++;
         e=(e+last)%w;
         a=edge[d].a;
         b=edge[d].b;
         if (p[a]==b)
         {
             parent=b;
             child=a;
         }
         else
         {
             parent=a;
             child=b;
         }
         nodes[parent].erase({child,edge[d].c});
         nodes[child].erase({parent,edge[d].c});
         edge[d].c=e;
         nodes[parent].insert({child,edge[d].c});
         nodes[child].insert({parent,edge[d].c});
         update(parent);
         cout << (*prev(rez.end())) << "\n";
         last=(*prev(rez.end()));
    }
    return 0;
}

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