Submission #447032

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
447032	2021-07-24T09:13:51 Z	yungyao	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	200 ms	6392 KB

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.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	204 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	204 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	9 ms	332 KB	Output is correct
5	Correct	42 ms	676 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	2 ms	332 KB	Output is correct
10	Correct	10 ms	332 KB	Output is correct
11	Correct	46 ms	804 KB	Output is correct
12	Correct	3 ms	588 KB	Output is correct
13	Correct	3 ms	588 KB	Output is correct
14	Correct	4 ms	588 KB	Output is correct
15	Correct	14 ms	660 KB	Output is correct
16	Correct	56 ms	1092 KB	Output is correct
17	Correct	61 ms	5736 KB	Output is correct
18	Correct	62 ms	5688 KB	Output is correct
19	Correct	62 ms	5700 KB	Output is correct
20	Correct	78 ms	5832 KB	Output is correct
21	Correct	200 ms	6384 KB	Output is correct