Submission #373729

#	Time	Username	Problem	Language	Result	Execution time	Memory
373729		LucaDantas	Dynamic Diameter (CEOI19_diameter)	C++17	24 / 100	2128 ms	5228 KiB

diameter

#include<bits/stdc++.h>
using namespace std;

constexpr int maxn = 1e5+10;

vector<pair<int,int>> g[maxn];

int n, q;
long long dist[maxn], cost[maxn], w;

void dfs(int u, int p) {
	for(auto [v, id] : g[u]) {
		if(v != p) {
			dist[v] = dist[u] + cost[id];
			dfs(v, u);
		}
	}
}

void brute() {
	int last = 0;
	while(q--) {
		int d, e; scanf("%d %d", &d, &e);
		d = (d + last) % (n - 1);
		e = (e + last) % w;
		cost[d] = e;
		dist[1] = 0;
		dfs(1, 0);
		int x = max_element(dist+1, dist+n+1) - dist;
		dist[x] = 0;
		dfs(x, 0);
		printf("%lld\n", *max_element(dist+1, dist+n+1));
		last = *max_element(dist+1, dist+n+1);
	}
	exit(0);
}

void bst() {
	multiset<int> st;
	for(int i = 0; i < n-1; i++)
		st.insert(cost[i]);
	int last = 0;
	while(q--) {
		int d, e; scanf("%d %d", &d, &e);
		d = (d + last) % (n - 1);
		e = (e + last) % w;
		st.erase(st.find(cost[d]));
		cost[d] = e;
		st.insert(e);
		last = *st.begin() + (n>2?*next(st.begin()):0);
		printf("%d\n", last);
	}
	exit(0);
}

int main() {
	scanf("%d %d %lld", &n, &q, &w);
	// printf("%d %d %lld\n", n, q, w);
	if(w > 10000) assert(0);
	for(int i = 0; i < n-1; i++) {
		int a, b; long long c; scanf("%d %d %lld", &a, &b, &c);
		// printf("%d %d %lld\n", a, b, c);
		g[a].push_back({b, i});
		g[b].push_back({a, i});
		cost[i] = c;
	}
	if(n <= 5000) brute();
	if((int)g[1].size() == n-1) bst();
}

Compilation message (stderr)

diameter.cpp: In function 'void brute()':
diameter.cpp:23:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   23 |   int d, e; scanf("%d %d", &d, &e);
      |             ~~~~~^~~~~~~~~~~~~~~~~
diameter.cpp: In function 'void bst()':
diameter.cpp:44:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   44 |   int d, e; scanf("%d %d", &d, &e);
      |             ~~~~~^~~~~~~~~~~~~~~~~
diameter.cpp: In function 'int main()':
diameter.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |  scanf("%d %d %lld", &n, &q, &w);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:61:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |   int a, b; long long c; scanf("%d %d %lld", &a, &b, &c);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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