Submission #447032

#	Time	Username	Problem	Language	Result	Execution time	Memory
447032		yungyao	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	200 ms	6392 KiB

diameter

using namespace std;
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <utility>
#include <memory.h>
#include <vector>
#include <bitset>

typedef pair<int,int> pii;
typedef long long LL;

#define iter(x) x.begin(),x.end()
#define F first
#define S second
#define pb push_back
#define mkp make_pair

#include <climits>
const int maxn = 1e5+100,mod = 0;

int mp[maxn],val[maxn];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n,q,w;

    cin >> n >> q >> w;
    multiset <LL> mst;
    for (int i=0;i<n-1;++i){
        int u,v;
        LL c;

        cin >> u >> v >> c;
        mp[i] = max(u,v);
        val[max(u,v)] = c;
        mst.insert(c);
    }

    LL last = 0;
    while (q--){
        int d; LL e;
        cin >> d >> e;
        
        d = (last + d) % (n-1);
        e = (last + e) % w;
        mst.erase(mst.find(val[mp[d]]));
        val[mp[d]] = e;
        mst.insert(e);

        last = *prev(mst.end()) + (n == 2 ? 0 : *prev(prev(mst.end())));
        cout << last << '\n';
    }

    return 0;
}

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