Submission #472627

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
472627	2021-09-13T22:33:20 Z	Ozy	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	261 ms	16460 KB

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

lli n,q,w,a,b,c,last,id;
lli peso[MAX+2];
vector<lli> hijos[MAX+2];
pair<lli,lli> arr[MAX+2];
multiset<lli> maximo;
multiset<lli>::iterator it;

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);

        arr[i] = {a,b};
        peso[i] = c;
        maximo.insert(-c);
    }

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

        //correcto
        cin >> id >> c;
        id += last;
        id %= (n-1);
        id++;
        c += last;
        c %= w;

        it = maximo.lower_bound(-peso[id]);
        maximo.erase(it);

        peso[id] = c;
        maximo.insert(-c);

        it = maximo.lower_bound(-w);
        a = *it;
        if (n > 2) {
            it++;
            b = *it;
            a += b;
        }
        a *= -1;

        cout << a << "\n";
        last = a;
    }
}

Subtask #1
0 / 11.0

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

Subtask #2
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	2636 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	2 ms	2636 KB	Output is correct
2	Correct	2 ms	2636 KB	Output is correct
3	Correct	3 ms	2636 KB	Output is correct
4	Correct	10 ms	2756 KB	Output is correct
5	Correct	40 ms	3012 KB	Output is correct
6	Correct	2 ms	2636 KB	Output is correct
7	Correct	2 ms	2636 KB	Output is correct
8	Correct	2 ms	2636 KB	Output is correct
9	Correct	3 ms	2636 KB	Output is correct
10	Correct	12 ms	2764 KB	Output is correct
11	Correct	51 ms	3092 KB	Output is correct
12	Correct	5 ms	3148 KB	Output is correct
13	Correct	5 ms	3148 KB	Output is correct
14	Correct	6 ms	3148 KB	Output is correct
15	Correct	19 ms	3276 KB	Output is correct
16	Correct	61 ms	4600 KB	Output is correct
17	Correct	78 ms	14768 KB	Output is correct
18	Correct	91 ms	14868 KB	Output is correct
19	Correct	101 ms	14772 KB	Output is correct
20	Correct	127 ms	15132 KB	Output is correct
21	Correct	261 ms	16460 KB	Output is correct