Submission #447031

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
447031	2021-07-24T09:05:29 Z	fhvirus	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	235 ms	15848 KB

diameter

// Knapsack DP is harder than FFT.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll;
#define ff first
#define ss second
#define pb emplace_back
#define AI(x) begin(x),end(x)
template<class I>bool chmax(I&a,I b){return a<b?(a=b,true):false;}
template<class I>bool chmin(I&a,I b){return b<a?(a=b,true):false;} 
#ifdef OWO
#define debug(args...) SDF(#args, args)
#define OIU(args...) ostream& operator<<(ostream&O,args)
#define LKJ(S,B,E,F) template<class...T>OIU(S<T...>s){O<<B;int c=0;for(auto i:s)O<<(c++?", ":"")<<F;return O<<E;}
LKJ(vector,'[',']',i)LKJ(deque,'[',']',i)LKJ(set,'{','}',i)LKJ(multiset,'{','}',i)LKJ(unordered_set,'{','}',i)LKJ(map,'{','}',i.ff<<':'<<i.ss)LKJ(unordered_map,'{','}',i.ff<<':'<<i.ss)
template<class...T>void SDF(const char* s,T...a){int c=sizeof...(T);if(!c){cerr<<"\033[1;32mvoid\033[0m\n";return;}(cerr<<"\033[1;32m("<<s<<") = (",...,(cerr<<a<<(--c?", ":")\033[0m\n")));}
template<class T,size_t N>OIU(array<T,N>a){return O<<vector<T>(AI(a));}template<class...T>OIU(pair<T...>p){return O<<'('<<p.ff<<','<<p.ss<<')';}template<class...T>OIU(tuple<T...>t){return O<<'(',apply([&O](T...s){int c=0;(...,(O<<(c++?", ":"")<<s));},t),O<<')';}
#else
#pragma GCC optimize("Ofast")
#define debug(...) ((void)0)
#endif

typedef tuple<int, int, ll> triple;

const int kN = 100001;
int n, q; ll w;
pii edg[kN]; ll wei[kN];
vector<pll> adj[kN];
int par[kN];
ll dep[kN], dp[kN];
multiset<ll> s;


void init(){
	for(int w = 0; w < n-1; ++w) s.insert(wei[w]);
}
void rm(ll v){
	auto it = s.find(v);
	s.erase(it);
}
ll upd(ll d, ll e){
	rm(wei[d]);
	wei[d] = e;
	s.insert(e);
	if(s.size() == 1) return *begin(s);
	return *prev(end(s)) + *prev(prev(end(s)));
}

signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> q >> w;
	for(int i = 0; i < n-1; ++i){
		int u, v; ll c; cin >> u >> v >> c;
		edg[i] = pii(u, v);
		wei[i] = c;
		adj[u].pb(v, i);
		adj[v].pb(u, i);
	}
	init();
	ll last = 0;
	for(int i = 0; i < q; ++i){
		ll d, e; cin >> d >> e;
		d = (d + last) % (n-1);
		e = (e + last) % w;
		cout << (last = upd(d, e)) << '\n';
	}
	return 0;
}

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	2780 KB	Output is correct
5	Correct	43 ms	3008 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	13 ms	2764 KB	Output is correct
11	Correct	50 ms	3140 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	16 ms	3332 KB	Output is correct
16	Correct	60 ms	3804 KB	Output is correct
17	Correct	74 ms	13532 KB	Output is correct
18	Correct	79 ms	13616 KB	Output is correct
19	Correct	75 ms	13548 KB	Output is correct
20	Correct	90 ms	13632 KB	Output is correct
21	Correct	224 ms	14752 KB	Output is correct