Submission #276126

#	Time	Username	Problem	Language	Result	Execution time	Memory
276126		egekabas	Dynamic Diameter (CEOI19_diameter)	C++14	24 / 100	5094 ms	27512 KiB

diameter

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<ll, ll> pii;
typedef pair<ld, ld> pld;
ll n, q, w;
pii edge[100009];
vector<ll> g[100009];
map<ll, ll> val[100009];

pii far = {-1e9, -1e9};
void dfs(ll v, ll prt, ll dis){
    far = max(far, {dis, v});
    for(auto u : g[v])
        if(u != prt)
            dfs(u, v, dis+val[v][u]);
}
ll finddia(){
    far = {-1e9, -1e9};
    dfs(1, 0, 0);
    ll cur = far.ss;
    far = {-1e9, -1e9};
    dfs(cur, 0, 0);
    return far.ff;
}
ll last;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    cin >> n >> q >> w;
    for(ll i = 0; i < n-1; ++i){
        cin >> edge[i].ff >> edge[i].ss >> val[edge[i].ff][edge[i].ss];
        val[edge[i].ss][edge[i].ff] = val[edge[i].ff][edge[i].ss];
        g[edge[i].ff].pb(edge[i].ss);
        g[edge[i].ss].pb(edge[i].ff);
    }
    while(q--){
        ll d, e;
        cin >> d >> e;
        d = (d+last)%(n-1);
        e = (e+last)%w;
        val[edge[d].ss][edge[d].ff] = val[edge[d].ff][edge[d].ss] = e;
        last = finddia();
        cout << last << '\n';
    }
}

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