# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
373734 | 2021-03-05T14:37:10 Z | LucaDantas | Dynamic Diameter (CEOI19_diameter) | C++17 | 2105 ms | 12768 KB |
#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<long long, greater<long long>> 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 = (int)((d + last) % (n - 1)); e = (int)((e + last) % w); st.erase(st.find(cost[d])); cost[d] = e; st.insert(e); last = (int)(*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((int)g[1].size() == n-1) bst(); if(n <= 5000) brute(); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2668 KB | Output is correct |
2 | Correct | 2 ms | 2668 KB | Output is correct |
3 | Correct | 2 ms | 2668 KB | Output is correct |
4 | Correct | 2 ms | 2796 KB | Output is correct |
5 | Correct | 2 ms | 2668 KB | Output is correct |
6 | Correct | 2 ms | 2668 KB | Output is correct |
7 | Correct | 2 ms | 2668 KB | Output is correct |
8 | Correct | 2 ms | 2668 KB | Output is correct |
9 | Correct | 2 ms | 2668 KB | Output is correct |
10 | Correct | 2 ms | 2668 KB | Output is correct |
11 | Correct | 2 ms | 2668 KB | Output is correct |
12 | Correct | 2 ms | 2668 KB | Output is correct |
13 | Correct | 2 ms | 2668 KB | Output is correct |
14 | Correct | 2 ms | 2668 KB | Output is correct |
15 | Correct | 2 ms | 2668 KB | Output is correct |
16 | Correct | 2 ms | 2668 KB | Output is correct |
17 | Correct | 2 ms | 2668 KB | Output is correct |
18 | Correct | 2 ms | 2668 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2668 KB | Output is correct |
2 | Correct | 2 ms | 2668 KB | Output is correct |
3 | Correct | 2 ms | 2668 KB | Output is correct |
4 | Correct | 2 ms | 2796 KB | Output is correct |
5 | Correct | 2 ms | 2668 KB | Output is correct |
6 | Correct | 2 ms | 2668 KB | Output is correct |
7 | Correct | 2 ms | 2668 KB | Output is correct |
8 | Correct | 2 ms | 2668 KB | Output is correct |
9 | Correct | 2 ms | 2668 KB | Output is correct |
10 | Correct | 2 ms | 2668 KB | Output is correct |
11 | Correct | 2 ms | 2668 KB | Output is correct |
12 | Correct | 2 ms | 2668 KB | Output is correct |
13 | Correct | 2 ms | 2668 KB | Output is correct |
14 | Correct | 2 ms | 2668 KB | Output is correct |
15 | Correct | 2 ms | 2668 KB | Output is correct |
16 | Correct | 2 ms | 2668 KB | Output is correct |
17 | Correct | 2 ms | 2668 KB | Output is correct |
18 | Correct | 2 ms | 2668 KB | Output is correct |
19 | Correct | 153 ms | 2796 KB | Output is correct |
20 | Correct | 166 ms | 2816 KB | Output is correct |
21 | Correct | 172 ms | 2796 KB | Output is correct |
22 | Correct | 207 ms | 2796 KB | Output is correct |
23 | Correct | 1131 ms | 3308 KB | Output is correct |
24 | Correct | 1247 ms | 3196 KB | Output is correct |
25 | Correct | 1312 ms | 3308 KB | Output is correct |
26 | Correct | 1581 ms | 3308 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2668 KB | Output is correct |
2 | Correct | 2 ms | 2668 KB | Output is correct |
3 | Correct | 3 ms | 2668 KB | Output is correct |
4 | Correct | 11 ms | 2796 KB | Output is correct |
5 | Correct | 46 ms | 3052 KB | Output is correct |
6 | Correct | 2 ms | 2668 KB | Output is correct |
7 | Correct | 2 ms | 2668 KB | Output is correct |
8 | Correct | 2 ms | 2668 KB | Output is correct |
9 | Correct | 3 ms | 2668 KB | Output is correct |
10 | Correct | 13 ms | 2796 KB | Output is correct |
11 | Correct | 53 ms | 3180 KB | Output is correct |
12 | Correct | 5 ms | 3180 KB | Output is correct |
13 | Correct | 5 ms | 3180 KB | Output is correct |
14 | Correct | 6 ms | 3180 KB | Output is correct |
15 | Correct | 17 ms | 3180 KB | Output is correct |
16 | Correct | 64 ms | 3692 KB | Output is correct |
17 | Correct | 76 ms | 12288 KB | Output is correct |
18 | Correct | 70 ms | 12000 KB | Output is correct |
19 | Correct | 74 ms | 12128 KB | Output is correct |
20 | Correct | 94 ms | 12128 KB | Output is correct |
21 | Correct | 215 ms | 12768 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 25 ms | 2796 KB | Output is correct |
2 | Correct | 217 ms | 2796 KB | Output is correct |
3 | Correct | 1065 ms | 3052 KB | Output is correct |
4 | Correct | 2105 ms | 3312 KB | Output is correct |
5 | Incorrect | 6 ms | 3180 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 5 ms | 5228 KB | Execution killed with signal 6 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2668 KB | Output is correct |
2 | Correct | 2 ms | 2668 KB | Output is correct |
3 | Correct | 2 ms | 2668 KB | Output is correct |
4 | Correct | 2 ms | 2796 KB | Output is correct |
5 | Correct | 2 ms | 2668 KB | Output is correct |
6 | Correct | 2 ms | 2668 KB | Output is correct |
7 | Correct | 2 ms | 2668 KB | Output is correct |
8 | Correct | 2 ms | 2668 KB | Output is correct |
9 | Correct | 2 ms | 2668 KB | Output is correct |
10 | Correct | 2 ms | 2668 KB | Output is correct |
11 | Correct | 2 ms | 2668 KB | Output is correct |
12 | Correct | 2 ms | 2668 KB | Output is correct |
13 | Correct | 2 ms | 2668 KB | Output is correct |
14 | Correct | 2 ms | 2668 KB | Output is correct |
15 | Correct | 2 ms | 2668 KB | Output is correct |
16 | Correct | 2 ms | 2668 KB | Output is correct |
17 | Correct | 2 ms | 2668 KB | Output is correct |
18 | Correct | 2 ms | 2668 KB | Output is correct |
19 | Correct | 153 ms | 2796 KB | Output is correct |
20 | Correct | 166 ms | 2816 KB | Output is correct |
21 | Correct | 172 ms | 2796 KB | Output is correct |
22 | Correct | 207 ms | 2796 KB | Output is correct |
23 | Correct | 1131 ms | 3308 KB | Output is correct |
24 | Correct | 1247 ms | 3196 KB | Output is correct |
25 | Correct | 1312 ms | 3308 KB | Output is correct |
26 | Correct | 1581 ms | 3308 KB | Output is correct |
27 | Correct | 2 ms | 2668 KB | Output is correct |
28 | Correct | 2 ms | 2668 KB | Output is correct |
29 | Correct | 3 ms | 2668 KB | Output is correct |
30 | Correct | 11 ms | 2796 KB | Output is correct |
31 | Correct | 46 ms | 3052 KB | Output is correct |
32 | Correct | 2 ms | 2668 KB | Output is correct |
33 | Correct | 2 ms | 2668 KB | Output is correct |
34 | Correct | 2 ms | 2668 KB | Output is correct |
35 | Correct | 3 ms | 2668 KB | Output is correct |
36 | Correct | 13 ms | 2796 KB | Output is correct |
37 | Correct | 53 ms | 3180 KB | Output is correct |
38 | Correct | 5 ms | 3180 KB | Output is correct |
39 | Correct | 5 ms | 3180 KB | Output is correct |
40 | Correct | 6 ms | 3180 KB | Output is correct |
41 | Correct | 17 ms | 3180 KB | Output is correct |
42 | Correct | 64 ms | 3692 KB | Output is correct |
43 | Correct | 76 ms | 12288 KB | Output is correct |
44 | Correct | 70 ms | 12000 KB | Output is correct |
45 | Correct | 74 ms | 12128 KB | Output is correct |
46 | Correct | 94 ms | 12128 KB | Output is correct |
47 | Correct | 215 ms | 12768 KB | Output is correct |
48 | Correct | 25 ms | 2796 KB | Output is correct |
49 | Correct | 217 ms | 2796 KB | Output is correct |
50 | Correct | 1065 ms | 3052 KB | Output is correct |
51 | Correct | 2105 ms | 3312 KB | Output is correct |
52 | Incorrect | 6 ms | 3180 KB | Output isn't correct |
53 | Halted | 0 ms | 0 KB | - |