# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
207957 | 2020-03-09T14:27:16 Z | E869120 | Dynamic Diameter (CEOI19_diameter) | C++14 | 2353 ms | 19704 KB |
#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
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 6520 KB | Output is correct |
2 | Correct | 9 ms | 6520 KB | Output is correct |
3 | Correct | 9 ms | 6520 KB | Output is correct |
4 | Correct | 10 ms | 6520 KB | Output is correct |
5 | Correct | 9 ms | 6520 KB | Output is correct |
6 | Correct | 9 ms | 6520 KB | Output is correct |
7 | Correct | 9 ms | 6520 KB | Output is correct |
8 | Correct | 9 ms | 6520 KB | Output is correct |
9 | Correct | 9 ms | 6520 KB | Output is correct |
10 | Correct | 9 ms | 6520 KB | Output is correct |
11 | Correct | 10 ms | 6520 KB | Output is correct |
12 | Correct | 9 ms | 6520 KB | Output is correct |
13 | Correct | 9 ms | 6520 KB | Output is correct |
14 | Correct | 9 ms | 6520 KB | Output is correct |
15 | Correct | 9 ms | 6520 KB | Output is correct |
16 | Correct | 9 ms | 6520 KB | Output is correct |
17 | Correct | 9 ms | 6524 KB | Output is correct |
18 | Correct | 10 ms | 6520 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 6520 KB | Output is correct |
2 | Correct | 9 ms | 6520 KB | Output is correct |
3 | Correct | 9 ms | 6520 KB | Output is correct |
4 | Correct | 10 ms | 6520 KB | Output is correct |
5 | Correct | 9 ms | 6520 KB | Output is correct |
6 | Correct | 9 ms | 6520 KB | Output is correct |
7 | Correct | 9 ms | 6520 KB | Output is correct |
8 | Correct | 9 ms | 6520 KB | Output is correct |
9 | Correct | 9 ms | 6520 KB | Output is correct |
10 | Correct | 9 ms | 6520 KB | Output is correct |
11 | Correct | 10 ms | 6520 KB | Output is correct |
12 | Correct | 9 ms | 6520 KB | Output is correct |
13 | Correct | 9 ms | 6520 KB | Output is correct |
14 | Correct | 9 ms | 6520 KB | Output is correct |
15 | Correct | 9 ms | 6520 KB | Output is correct |
16 | Correct | 9 ms | 6520 KB | Output is correct |
17 | Correct | 9 ms | 6524 KB | Output is correct |
18 | Correct | 10 ms | 6520 KB | Output is correct |
19 | Correct | 301 ms | 7032 KB | Output is correct |
20 | Correct | 332 ms | 6776 KB | Output is correct |
21 | Correct | 325 ms | 6776 KB | Output is correct |
22 | Correct | 372 ms | 6780 KB | Output is correct |
23 | Correct | 1995 ms | 7288 KB | Output is correct |
24 | Correct | 2123 ms | 7368 KB | Output is correct |
25 | Correct | 2212 ms | 7288 KB | Output is correct |
26 | Correct | 2353 ms | 7792 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 6520 KB | Output is correct |
2 | Correct | 11 ms | 6520 KB | Output is correct |
3 | Correct | 11 ms | 6520 KB | Output is correct |
4 | Incorrect | 13 ms | 6904 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 57 ms | 6648 KB | Output is correct |
2 | Incorrect | 12 ms | 6776 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 126 ms | 19704 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 6520 KB | Output is correct |
2 | Correct | 9 ms | 6520 KB | Output is correct |
3 | Correct | 9 ms | 6520 KB | Output is correct |
4 | Correct | 10 ms | 6520 KB | Output is correct |
5 | Correct | 9 ms | 6520 KB | Output is correct |
6 | Correct | 9 ms | 6520 KB | Output is correct |
7 | Correct | 9 ms | 6520 KB | Output is correct |
8 | Correct | 9 ms | 6520 KB | Output is correct |
9 | Correct | 9 ms | 6520 KB | Output is correct |
10 | Correct | 9 ms | 6520 KB | Output is correct |
11 | Correct | 10 ms | 6520 KB | Output is correct |
12 | Correct | 9 ms | 6520 KB | Output is correct |
13 | Correct | 9 ms | 6520 KB | Output is correct |
14 | Correct | 9 ms | 6520 KB | Output is correct |
15 | Correct | 9 ms | 6520 KB | Output is correct |
16 | Correct | 9 ms | 6520 KB | Output is correct |
17 | Correct | 9 ms | 6524 KB | Output is correct |
18 | Correct | 10 ms | 6520 KB | Output is correct |
19 | Correct | 301 ms | 7032 KB | Output is correct |
20 | Correct | 332 ms | 6776 KB | Output is correct |
21 | Correct | 325 ms | 6776 KB | Output is correct |
22 | Correct | 372 ms | 6780 KB | Output is correct |
23 | Correct | 1995 ms | 7288 KB | Output is correct |
24 | Correct | 2123 ms | 7368 KB | Output is correct |
25 | Correct | 2212 ms | 7288 KB | Output is correct |
26 | Correct | 2353 ms | 7792 KB | Output is correct |
27 | Correct | 10 ms | 6520 KB | Output is correct |
28 | Correct | 11 ms | 6520 KB | Output is correct |
29 | Correct | 11 ms | 6520 KB | Output is correct |
30 | Incorrect | 13 ms | 6904 KB | Output isn't correct |
31 | Halted | 0 ms | 0 KB | - |