Submission #472624

#	Time	Username	Problem	Language	Result	Execution time	Memory
472624		Ozy	Dynamic Diameter (CEOI19_diameter)	C++17	24 / 100	5100 ms	27420 KiB

diameter

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define MAX 100000
#define dis first
#define prof second

lli n,q,w,a,b,c,last;
vector<lli> hijos[MAX+2];
map<lli,lli> mapa[MAX+2];
pair<lli,lli> arr[MAX+2];
pair<lli,lli> res;

pair<lli,lli> busca(lli pos, lli padre) {

    bool hoja=true;
    pair<lli,lli> act,ult;

    ult.dis = 0;
    for (auto h : hijos[pos]) {
        if(h == padre) continue;

        hoja = false;
        act = busca(h,pos);
        act.dis += mapa[pos][h];

        if (act.dis > ult.dis) ult = act;
    }

    if (hoja) return{0,pos};
    else return ult;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> q >> w;
    rep(i,1,n-1) {
        cin >> a >> b >> c;
        hijos[a].push_back(b);
        hijos[b].push_back(a);
        mapa[a][b] = c;
        mapa[b][a] = c;

        arr[i] = {a,b};
    }

    last = 0;
    rep(i,1,q) {

        cin >> a >> c;
        a += last;
        a %= (n-1);
        a++;
        c += last;
        c %= w;

        b = arr[a].first;
        a = arr[a].second;
        mapa[a][b] = c;
        mapa[b][a] = c;

        res = busca(1,0);
        res = busca(res.second,0);

        cout << res.dis << "\n";
        last = res.dis;
    }
}

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