Submission #207957

#	Time	Username	Problem	Language	Result	Execution time	Memory
207957		E869120	Dynamic Diameter (CEOI19_diameter)	C++14	24 / 100	2353 ms	19704 KiB

diameter

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <functional>
using namespace std;
#pragma warning (disable: 4996)

// Input
long long N, A[1 << 18], B[1 << 18], C[1 << 18];
long long Q, D[1 << 18], E[1 << 18];
long long W;
vector<pair<int, long long>> X[1 << 18];

// Some Information
long long dist[1 << 18];

// Subtask 2
void dfs1(int pos, long long dep) {
	dist[pos] = dep;
	for (int i = 0; i < X[pos].size(); i++) {
		if (dist[X[pos][i].first] != (1LL << 60)) continue;
		dfs1(X[pos][i].first, dep + X[pos][i].second);
	}
}

void getdist(int pos) {
	for (int i = 1; i <= N; i++) dist[i] = (1LL << 60);
	dfs1(pos, 0);
}

long long solve1() {
	for (int i = 1; i <= N; i++) X[i].clear();
	for (int i = 1; i <= N - 1; i++) {
		X[A[i]].push_back(make_pair(B[i], C[i]));
		X[B[i]].push_back(make_pair(A[i], C[i]));
	}
	getdist(1);
	pair<long long, int> maxn1 = make_pair(-1, -1);
	for (int i = 1; i <= N; i++) maxn1 = max(maxn1, make_pair(dist[i], i));
	getdist(maxn1.second);
	pair<long long, int> maxn2 = make_pair(-1, -1);
	for (int i = 1; i <= N; i++) maxn2 = max(maxn2, make_pair(dist[i], i));
	return maxn2.first;
}

void solve_subtask2() {
	long long last = 0;
	for (int i = 1; i <= Q; i++) {
		D[i] = (D[i] + last) % (N - 1LL) + 1LL;
		E[i] = (E[i] + last) % W;
		C[D[i]] = E[i];
		last = solve1();
		printf("%lld\n", last);
	}
}

int main() {
	scanf("%lld%lld%lld", &N, &Q, &W);
	for (int i = 1; i <= N - 1; i++) {
		scanf("%lld%lld%lld", &A[i], &B[i], &C[i]);
		X[A[i]].push_back(make_pair(B[i], C[i])); 
		X[B[i]].push_back(make_pair(A[i], C[i])); 
	}
	for (int i = 1; i <= Q; i++) scanf("%lld%lld", &D[i], &E[i]);

	if (N <= 5000 && Q <= 5000) {
		solve_subtask2();
	}
	return 0;
}

Compilation message (stderr)

diameter.cpp:9:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
diameter.cpp: In function 'void dfs1(int, long long int)':
diameter.cpp:23:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < X[pos].size(); i++) {
                  ~~^~~~~~~~~~~~~~~
diameter.cpp: In function 'int main()':
diameter.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld", &N, &Q, &W);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld", &A[i], &B[i], &C[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
diameter.cpp:67:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= Q; i++) scanf("%lld%lld", &D[i], &E[i]);
                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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